(von this post auf fshub Edited)
Das erste Mal, dass ich für Pause/weiter in OCaml/F # erreichen ging, warf mich für eine (unendliche) Schleife, sozusagen, weil so etwas nicht existiert! In OCaml kann man Exceptions verwenden, um aus einer Schleife auszubrechen, weil sie sehr sind, aber in F # (in.NET) der Overhead ist ziemlich hoch und nicht nützlich für "normale" Flusskontrolle.
Das kam, wenn man vor einiger Zeit mit Sortieralgorithmen spielte (um etwas Zeit zu verlieren), die repeat/bis und break stark nutzen. Mir ist aufgefallen, dass rekursive Tail-Call-Funktionen genau das gleiche Ergebnis erzielen können, mit nur geringer Lesbarkeit. Also habe ich 'veränderliches bDone' und 'when not bDone' weggeworfen und habe versucht, den Code ohne diese imperativen Konstrukte zu schreiben. Im Folgenden werden nur die Schleifenpartitionen herausgefiltert, und es wird gezeigt, wie mit Wiederholungsrufen der Code repeat/bis, do/while, while/do, break/continue und Test-in-the-middle-style geschrieben wird. Diese scheinen alle genau so schnell zu laufen wie eine traditionelle F # 'while'-Anweisung, aber Ihre Laufleistung kann variieren (einige Plattformen implementieren möglicherweise nicht richtig einen Heckruf und können deshalb Fehler stapeln, bis sie gepatcht sind). Am Ende ist ein (schlechter) Sortieralgorithmus in beiden Stilen zum Vergleich geschrieben. Beginnen wir mit einer 'do/while'-Schleife, die im traditionellen F # -Imperativstil geschrieben ist, und betrachten dann funktionale Variationen, die sowohl die gleiche Art von Schleifen als auch verschiedene Semantiken wie while/do, repeat/bis, Test in der Mitte, und sogar brechen/weiter (ohne Monaden .. ähm, Workflows!).
#light
(* something to work on... *)
let v = ref 0
let f() = incr v;
let g() = !v;
let N = 100000000
let imperDoWhile() =
let mutable x = 0
let mutable bDone = false
while not bDone do
f()
x <- x + 1
if x >= N then bDone <- true
Ok, das ist einfach genug. Beachten Sie, dass f() immer mindestens einmal (do/while) aufgerufen wird.
Hier ist der gleiche Code, aber in einem funktionalen Stil. Beachten Sie, dass wir hier keine Mutable deklarieren müssen.
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
Wir können das zu einem traditionellen do/while drehen, indem wir den Funktionsaufruf in den if-Block setzen.
Wie wäre es, einen Block zu wiederholen, bis eine Bedingung erfüllt ist (Wiederholung/bis)? Einfach genug ...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then() (*Until*)
else loop (x+1)
loop 0
Was war das mit einer monad-losen Pause? Nun, führen Sie einfach einen Bedingungsausdruck ein, der 'Einheit' zurückgibt, wie in:
Wie weiter? Nun, das ist nur ein weiterer Aufruf zum Loop! Zuerst mit einer Syntax Krücke:
let funBreakContinue() =
let break'() =()
let rec continue'() =
let x = g()
if x > N then break'()
elif x % 2 = 0 then
f(); f(); f();
continue'()
else
f()
continue'()
continue'()
Und dann wieder, ohne die (hässlich) Syntax Krücke:
let funBreakContinue'() =
let rec loop() =
let x = g()
if x > N then()
elif x % 2 = 0 then
f(); f(); f();
loop()
else
f()
loop()
loop()
Einfach als Torte!
Ein nettes Ergebnis dieser Schleifenformen ist, dass es das Erkennen und Implementieren von Zuständen in Ihren Schleifen erleichtert. Zum Beispiel wird bei einer Bubble-Sortierung das gesamte Array kontinuierlich durchlaufen, wobei Werte ausgetauscht werden, die beim Suchen fehl am Platz sind. Es verfolgt, ob ein Durchlauf über das Array einen Austausch auslöste. Wenn nicht, dann muss jeder Wert an der richtigen Stelle sein, damit die Sortierung enden kann. Als Optimierung wird bei jedem Durchgang durch das Array der letzte Wert im Array an der richtigen Stelle sortiert. So kann die Schleife jedes Mal um eins verkürzt werden. Die meisten Algorithmen suchen nach einem Austausch und aktualisieren jedes Mal, wenn es einen "bModified" -Flag gibt. Sobald der erste Austausch abgeschlossen ist, ist diese Zuweisung jedoch nicht mehr erforderlich. Es ist bereits wahr!
Hier ist F # Code, der eine Blasensortierung implementiert (ja, Blasensortierung ist ein schrecklicher Algorithmus; quicksort rockt). Am Ende ist eine imperative Implementierung, die den Zustand nicht ändert; Es aktualisiert das bModified-Flag für jeden Austausch.Interessanterweise ist die imperative Lösung bei kleinen Arrays schneller und bei großen nur um ein oder zwei Prozent langsamer. (Für ein gutes Beispiel gemacht).
let inline sort2 f i j (a:'a array) =
let i' = a.[ i ]
let j' = a.[ j ]
if f i' j' > 0 then
a.[ i ] <- j'
a.[ j ] <- i'
let bubble f (xs:'a array) =
if xs.Length = 0
then()
let rec modified i endix =
if i = endix then
unmodified 0 (endix-1)
else
let j = i+1
sort2 f i j xs
modified j endix
and unmodified i endix =
if i = endix then
()
else
let j = i+1
let i' = xs.[ i ]
let j' = xs.[ j ]
if f i' j' > 0 then
xs.[ i ] <- j'
xs.[ j ] <- i'
modified j endix
else
unmodified j endix
in unmodified 0 (xs.Length-1)
let bubble_imperitive f (xs:'a array) =
let mutable bModified = true
let mutable endix = xs.Length - 1
while bModified do
bModified <- false
endix <- endix - 1
for i in 0..endix do
let j = i+1
let i' = xs.[ i ]
let j' = xs.[ j ]
if f i' j' > 0 then
xs.[ i ] <- j'
xs.[ j ] <- i'
bModified <- true
done
done
Sollte wahrscheinlich Community-Wiki sein - keine "Antwort" an sich? – Anthony
@ Anthony, ich hoffe, es gibt eine Website, aber wenn nicht, dann mache ich diese. – Unknown
Sieht so aus, als hättest du diese Community zu früh gemacht - check-out pleac-ocaml – Thelema