SML: wie Liste zu Unterliste listet

Question

Ich habe diese Frage von CS 217 gefunden.

Teilen Sie eine Liste in eine oder mehrere Unterlisten auf, so dass jede Unterliste Ganzzahlen in nicht abnehmender (sortierter) Reihenfolge enthält.

[3,5,1,8,9,2,1,0] zurück [[3,5], [1,8,9], [2], [1], [0]

]

[1,2,3,4,5,6] returns [[1,2,3,4,5,6]]

[5,4,3,2,1] zurückkehrt [5 [], [4], [3], [2], [1]]

folgenden Code funktioniert:

val Q1 = [ 3, 5, 1, 8, 9, 2, 1, 0 ] 

val A1 = foldl (
    fn (x, a) => 
     if x > hd (hd a) then (x::hd a)::tl a 
     else [x]::a 
    ) [ [ hd Q1 ] ] (tl Q1) 

val A1 = map rev (rev A1) 

oder wie folgt aus: 2 verwenden temporär y Liste zu sammeln.

fun split l = let 
    fun split' tmp subset = 
     fn [] => [] 
     | [x] => (x::tmp)::subset 
     | (a::(c as b::_)) => 
       if a < b then split' (a::tmp) subset c 
       else split' [] ((a::tmp)::subset) c 
    in (rev o map rev) (split' [] [] l) end 

So viele Lösungen für diese Frage, Aber ich will noch wissen, wie es als Spiel Muster zu codieren Funktion? vielleicht etwas wie unten: (? Nicht sicher, ob es möglich ist)

fun split [] = [[]] 
| split [x] = [[x]] 
| split [a, b] = if a < b then (* here *) else (* here *) 
| split (a::b) = if a < hd b then (* here *) else (* here *) 

Diese Frage steckte mich wirklich.

Answer 1

Unter der Annahme, dass diese Hausaufgaben, ich zögere, eine vollständige Antwort zu geben, aber hier sind ein paar Hinweise:

1) Im leeren Grundlage Fall denke ich, dass Sie [[]] anstatt [] zurückkehren möchten. Ihre Spezifikation adressiert dies nicht, aber da die leere Liste die längste Liste von nicht abnehmenden ganzen Zahlen ist, die von der Vorderseite der leeren Liste gezogen werden können, sollte der Rückgabewert die Liste sein, die aus der leeren Liste besteht. Dies ist etwas ähnlich zu der Tatsache, dass das Powerset (Menge aller Untermengen) der leeren Menge die Menge ist, die die leere Menge enthält, und nicht die leere Menge selbst. Es sollte keine Rolle, wie Sie zu diesem besonderen Fall definieren, da die eigentliche Grundlage Fall ist ...

2) Im [x] Fall, dass Sie wirklich [[x]] zurückkehren müssen, anstatt [x], da die Art der Funktion, die Sie zu schreiben versucht, ist int list -> int list list

3) im verbleibenden Fall, dass Sie das Muster wie

schreiben

| split (x::y::zs) = (* fill this in *) 

dann testen, ob x <= y zu entscheiden, was zu tun ist. Da sowohl als auch x > ysplit (y::zs) beinhalten, könnten Sie dies einmal berechnen, geben Sie diesem einen Namen in einer let Bindung und haben Sie die if im Rahmen dieser Bindung, obwohl das meistens eine Frage des Geschmacks ist.

Beachten Sie, wie das Muster in diesem letzten Fall funktioniert.Explizite Verwendung von hd sollte in Funktionsdefinitionen, die Pattern-Matching verwenden, relativ selten sein (wenn Sie jedoch den letzten Fall ohne eine Pattern-Matching let Bindung ausarbeiten, werden Sie gezwungen sein, es in mindestens einem der Zweige des if zu verwenden).

Auf Edit: Da dies nicht Hausaufgaben, hier ist eine vollständige Implementierung:

fun split [] = [[]] 
| split [x] = [[x]] 
| split (x::y::zs) = 
    let val first::rest = split (y::zs) in 
     if x <= y then 
      (x::first) :: rest 
     else 
      [x]::first::rest 
    end;