Wie man eine rekursive Funktion in diesem Fall (SML) stoppt

Question

Wenn L [1,2,3] ist, dann möchte ich ein [[1,2,3], [2,3,1] , [3,1,2]].

Da jedes Mal, wenn ich die erste Zahl an das Ende anfügen, dann wenn L = [] dann funktioniert [hier nicht.

Wie die Funktion zu stoppen, sobald es die drei Listen hat?

Answer 1

Sie können einen Parameter x in der Funktion haben, um zu verfolgen, wie viele Ebenen tief in der Rekursion Sie sind.

fun p(L, x) = 
    if x < length(L) then [L] @ p(tl(L) @ [hd(L)], x+1) 
    else []; 

Dann rufen Sie die Funktion mit x = 0.

p([1, 2, 3], 0) 

Und wenn Sie mögen die zusätzlichen Parameter nicht, dann, wie Sie wahrscheinlich wissen, dass Sie eine andere Funktion definieren und es gleich die p-Funktion mit dem Parameter auf 0.

fun p0(L) = p(L, 0); 

p0([1, 2, 3]); (* same result as p([1, 2, 3], 0); *) 

Answer 2

gezwungen machen Lassen Sie mich noch einige Implementierungsvarianten zeigen. Zunächst einmal wollen wir eine Hilfsfunktion definieren, die eine Liste 1 Position nach links dreht:

(* operates on non-empty lists only *) 
fun rot1_left (h :: tl) = tl @ [h] 

Dann wird die p Funktion wie folgt definiert werden:

fun p xs = 
    let 
    (* returns reversed result *) 
    fun loop [] _ _ = [] 
     | loop xs n res = 
      if n = 0 
      then res 
      else loop (rot1_left xs) (n-1) (xs :: res) 
    in 
     List.rev (loop xs (length xs) []) 
    end 

Es ist in der Regel besser (Performance (-wise), um neue Elemente am Anfang der Liste hinzuzufügen und dann die resultierende Liste einmal umzukehren, dann an das Ende viele Male anzuhängen. Hinweis: Diese Version dreht sich am Ende falsch und ich hätte es optimieren können, aber nicht, um Code klarer zu machen.

Wir haben die Länge der gegebenen Liste berechnet, um ihre gedrehten "Kopien" zu machen, aber wir müssen xs nicht vorher durchlaufen, wir können es tun, wie wir es drehen. Also können wir xs als eine Art Zähler verwenden, der rekursiv die loop Hilfsfunktion auf dem Ende der xs Liste aufruft.

fun p xs = 
    let 
    (* returns reversed result *) 
    fun loop [] _  _ = [] 
     | loop xs []  res = res 
     | loop xs (_::tl) res = 
      loop (rot1_left xs) tl (xs :: res) 
    in 
     List.rev (loop xs xs []) 
    end 

das getan haben, sind wir jetzt näher p als foldl Funktion zur Umsetzung:

fun p xs = 
    (List.rev o #1) 
     (List.foldl 
     (fn (_, (res, rot)) => (rot::res, rot1_left rot)) 
     ([], xs) 
     xs) 

Das zweite Argument der List.foldl Funktion ist unser „Akkumulator“, die hier als vertreten Paar des aktuellen (Teil-) Ergebnisses wie in den vorherigen Implementierungen und der aktuellen gedrehten Liste. Das erklärt (List.rev o #1) Teil: Wir müssen die erste Komponente des Akkumulators nehmen und es umkehren. Und wie für den ([], xs) Teil - das aktuelle Ergebnis ist am Anfang leer (daher) und wir beginnen die erste xs Liste zu drehen. Auch die _ in (_, (res, rot)) bedeutet das aktuelle Element der gegebenen xs, die uns nicht interessiert, da es nur als ein Zähler dient (siehe die vorherige Variante).

Hinweis: o steht für die Funktionszusammensetzung in Standard ML.