Liste der Funktionalen code-snippets für Prozedurale Programmierer?[geschlossen]
https://stackoverflow.com/questions/832569
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Manchmal habe ich immer noch nicht weiterkommen, versucht zu übersetzen prozeduralen code in funktionalen code.
Gibt es eine Liste von funktionellen Idiome/snippets zugeordnet werden prozedurale Idiome/snippets?
Bearbeiten
Da scheint es nicht zu sein, eine zentrale website von diesen Schnipsel, ich bin drehen Sie diesen in eine community-wiki.Bitte fügen Sie in einer prozeduralen -> funktionale snippets hier.
Lösung
(Bearbeitet von dieser Beitrag auf fshub)
Das erste mal ging ich zu erreichen Pause/fortsetzen in OCaml/F#, es warf mich für eine (unendliche) Schleife, so zu sprechen, weil so etwas nicht existiert!In OCaml können Sie Ausnahmen zu brechen, aus einer Schleife, da Sie sehr Billig, aber in F# (in .NET) der Aufwand ist Recht hoch und nicht nützlich für die "normalen" flow control.
Dies kam beim spielen Sortieren-algorithmen eine Weile zurück (um zu töten einige Zeit, die schweren Einsatz wiederholen/bis und Pause.Es traf mich, dass rekursive tail-call-Funktionen erreichen kann, genau das gleiche Ergebnis, nur eine leichte ding, um die Lesbarkeit zu verbessern.Also, ich warf 'veränderlich bDone' und 'während nicht bDone' und versucht, den Quellcode zu schreiben, ohne diese imperative Konstrukte.Die folgenden destilliert aus, nur die looping-Teile und zeigt, wie Sie schreiben wiederholt/, bis, do/while, while/do, Pause/weiter, und testen-in-the-middle-Stil-code mit tailcalls.Diese scheinen alle zu laufen an genau der gleichen Geschwindigkeit wie eine herkömmliche F# 'while' Anweisung, aber Ihre Laufleistung kann variieren (einige Plattformen möglicherweise nicht ordnungsgemäß umzusetzen tailcall und kann daher stack-Fehler, bis Sie gepatcht sind).Am Ende befindet sich eine (schlechte) Sortieren Algorithmus geschrieben, in beiden Stilen, zum Vergleich.
Beginnen wir mit einer "do/while" Schleife, geschrieben in der traditionellen F# imperativen Stil, betrachten Sie dann die funktionale Varianten, die beide die gleiche Art von Schleife, sowie unterschiedliche Semantik wie während/do, repeat/until-test in der Mitte, und sogar Pause/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 leicht genug.Beachten Sie, dass f() wird immer dann aufgerufen, mindestens einmal (do/while).
Hier ist der gleiche code, aber in einem funktionalen Stil.Beachten Sie, dass wir nicht brauchen, um erklären eine veränderbare hier.
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
Wir können drehen, die auf einer traditionellen, do/while, indem Sie die Funktion rufen Sie innerhalb des if-Blocks.
let funWhileDo() =
let rec loop x =
if x < N then (*While*)
f() (*Do*)
loop (x+1)
loop 0
Wie über eine Wiederholung blockiert, bis eine bestimmte Bedingung wahr ist (wiederholen/bis)?Leicht genug...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then () (*Until*)
else loop (x+1)
loop 0
Was war das etwa eine Monade-weniger Pause?Gut, nur die Einführung einer bedingten Ausdruck "Einheit", wie in:
let funBreak() =
let rec loop() =
let x = g()
if x > N then () (*break*)
else
f()
loop()
loop()
Wie über weiter?Gut, das ist nur ein weiterer Aufruf von loop!Erste, mit einem 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ässliche) 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()
Easy as pie!
Ein schönes Ergebnis dieser Schleife Formen ist, dass es macht es einfacher zu finden und zu implementieren, die Staaten in Ihre Schleifen.Zum Beispiel, ein bubble-sort-beständig Schleifen über ein array, swapping Werte, die außerhalb der Stelle, an der es Sie findet.Sie merkt sich, ob Sie einen pass über das array erzeugt keine Austausch.Wenn nicht, dann wird jeder Wert muss in der richtigen Stelle, so ist die Sortierung beendet.Als Optimierung, bei jedem Durchgang durch das array, wird der Letzte Wert im array endet sortiert in der richtigen Stelle.Also, die Schleife kann verkürzt werden, indem man jedes mal durch.Die meisten algorithmen prüfen, ob ein swap-und update-eine "bModified" flag jedes mal, wenn es einen gibt.Sobald jedoch die ersten swap ist getan, es ist keine Notwendigkeit für die Aufgabe;es ist bereits auf true gesetzt!
Hier ist F# - code implementiert ein bubble-sort (ja, der bubble-sort ist schrecklich-Algorithmus;quicksort-Felsen).Am Ende ist zwingend erforderlich, die Umsetzung, die sich nicht ändern Zustand;es aktualisiert die bModified-flag für jedes exchange.Interessanterweise, den Imperativ der Lösung schneller auf die kleinen arrays und nur ein Prozent oder zwei langsamer auf großen.(Für ein gutes Beispiel, obwohl).
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
Andere Tipps
Oh, das ist jetzt eine nette Frage. Hier sind einige, Code snips in Python oder etwas cloe:
-
für Schleifen kann mit Iteratoren ersetzt werden
stripped_list = [line.strip() for line in line_list] -
für Schleifen kann mit anwenden oder einer Karte oder Filter ersetzt wird
Karte (oben, [ 'Satz', 'Fragment']) [ 'SENTENCE', 'FRAGMENT']
-
verschachtelt for-Schleifen mit der Zusammensetzung von Funktionen
-
Endrekursion anstelle von Schleifen
-
Generator Ausdrücke anstelle von for-Schleifen
sum(x*x for x in range(10))
Alte Hausaufgaben Frage:
Die Funktion
(define f-imperative (y) (x) ; x is a local variable
(begin
(set x e)
(while (p x y)
(set x (g x y)))
(h x y)))
ist in einem typischen zwingend notwendig, Stil, mit Zuordnung und Looping. Schreibe eine äquivalente Funktion f funktionelle, die nicht die Merkmale zwingend notwendig beginnen nicht verwenden (Sequenzierung), während (goto) und SET (Zuweisung). Sie können so viele `` Hilfsfunktionen verwenden ‚‘, wie Sie möchten, solange sie verwenden definiert lassen oder letrec und nicht auf höchster Ebene.
Eine Lösung:
; The idea is simple:
; Use parameter passing for binding the values
; of the variables and recursion instead of iteration.
;
; For those who like theory this is the main argument for proving
; that recursive functions (LISP, lambda calculus) have the same
; computational power as any imperative programming language.
(define f-functional (y)
(letrec (
(f-helper (lambda (x y)
(if (p x y)
(f-helper (g x y) y)
(h x y)))))
(f-helper e y)))
; Notice that y in f-helper is invariant. Therefore, we can rewrite
; f-helper without y as follows.
(define f-functional (y)
(letrec (
(f-helper (lambda (x)
(if (p x y)
(f-helper (g x y))
(h x y)))))
(f-helper e)))
; This is not the only solution, though I think it is one of the
; nicer ones.
Die Falte ist eine sehr interessante Funktion, die in vielen funktionalen Algorithmen ist von zentraler Bedeutung. Lassen Sie uns sagen, dass wir alle Elemente einer Liste hinzufügen möchten. In prozeduralen Code, würden Sie in der Regel einen Akkumulator Variable erstellen und setzen Sie sich auf 0, dann durch die Liste durchlaufen und den Akkumulator durch den Punkt erhöhen.
In Ocaml, führen Sie die gleiche Aktion in einer funktionalen Weise durch die Verwendung fach:
List.fold_left (+) 0 [1; 2; 3];;
- : int = 6
Mit Falte, können Sie zum Beispiel die Anzahl der Wörter in der Liste zählen und sie zugleich verketten:
List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")
Eine weitere nützliche Verwendung von fold ist ein Vektor in einen Satz zu kopieren. Als Sätze in Ocaml unveränderlich sind, müssen Sie effektiv für jedes Element der Liste einen neuen Satz erstellen, die den vorherigen Satz zuzüglich diesem neuen Element enthält.
module Int = struct type t = int let compare = compare end;;
module IntSet = Set.Make(Int);;
let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];;
val s : IntSet.t = <abstr>
IntSet.elements s;;
- : IntSet.elt list = [1; 2; 3]
Hier unser erstes Objekt eine leere Menge ist, und bei jedem Aufruf wird ein neuer Satz erstellt, basierend auf dem vorherigen Satz und die aktuellen Position durch IntSet.add verwendet wird.
Implement falten rekursiv einmal selbst, zu wissen, wie es unter der Haube getan wird, dann verwenden Sie die integrierte Version überall. Auch in C ++, mit std :: accumulate !
Das Pléac Projekt hat fast genau dies als Ziel - Umsetzung alle Beispiele in Perl Kochbuch in anderen Sprachen. Here'a die Links zu den ocaml-Version (das ist eine von drei 100% abgeschlossen) http: / /pleac.sourceforge.net/pleac_ocaml/index.html
