Elenco di frammenti di codice funzionali per programmatori procedurali? [chiuso]
https://stackoverflow.com/questions/832569
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
A volte rimango bloccato nel tentativo di tradurre il codice procedurale in codice funzionale.
Esiste un elenco di idiomi / snippet funzionali che sono associati a idiomi / snippet procedurali?
Modifica
Dato che non sembra esserci un sito web centralizzato di questi frammenti, lo sto trasformando in un wiki della comunità. Incolla qualsiasi procedura - > frammenti funzionali qui.
Soluzione
(modificato da questo post su fshub )
La prima volta che sono andato a cercare break / continue in OCaml / F #, mi ha lanciato un ciclo (infinito), per così dire, perché non esiste nulla del genere! In OCaml, si possono usare le eccezioni per uscire da un ciclo perché sono molto economici, ma in F # (in .NET) l'overhead è piuttosto elevato e non utile per "normale". controllo del flusso.
Questo è emerso quando si giocava con algoritmi di ordinamento qualche tempo fa (per ammazzare un po 'di tempo), che fanno un uso pesante di ripetizione / fino e interruzione. Mi ha colpito il fatto che le funzioni di chiamata di coda ricorsive possano ottenere esattamente lo stesso risultato, con solo una leggera influenza sulla leggibilità. Così, ho buttato fuori "mutable bDone" e "while not bDone" e ho provato a scrivere il codice senza questi costrutti imperativi. Di seguito vengono descritte solo le parti in loop e viene illustrato come scrivere ripetizione / until, do / while, while / do, break / continue e testare il codice di stile usando i tailcall. Questi sembrano funzionare esattamente alla stessa velocità di un'istruzione F # 'while' tradizionale, ma il tuo chilometraggio può variare (alcune piattaforme potrebbero non implementare correttamente il tailcall e quindi potrebbero accumulare guasti fino a quando non vengono patchate). Alla fine c'è un (cattivo) algoritmo di ordinamento scritto in entrambi gli stili, per il confronto.
Iniziamo con un ciclo 'do / while', scritto nel tradizionale stile imperativo F #, quindi esaminiamo le variazioni funzionali che forniscono sia lo stesso tipo di ciclo, sia diverse semantiche come while / do, repeat / until, test nel mezzo e persino interrompere / continuare (senza monadi ... um, flussi di lavoro!).
#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, è abbastanza facile. Tieni presente che f () viene sempre chiamato almeno una volta (do / while).
Ecco lo stesso codice, ma in uno stile funzionale. Nota che qui non è necessario dichiarare un parametro modificabile.
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
Siamo in grado di farlo ruotare su un do / while tradizionale inserendo la chiamata di funzione all'interno del blocco if.
let funWhileDo() =
let rec loop x =
if x < N then (*While*)
f() (*Do*)
loop (x+1)
loop 0
Che ne dici di ripetere un blocco fino a quando una condizione è vera (ripeti / fino a)? Abbastanza facile ...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then () (*Until*)
else loop (x+1)
loop 0
Cos'era quella di una pausa senza monade? Bene, basta introdurre un'espressione condizionale che restituisce 'unit', come in:
let funBreak() =
let rec loop() =
let x = g()
if x > N then () (*break*)
else
f()
loop()
loop()
Che ne dici di continuare? Bene, questa è solo un'altra chiamata da ripetere! Innanzitutto, con una stampella per la sintassi:
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'()
E poi di nuovo senza la (brutta) stampella di sintassi:
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()
Facile come una torta!
Un buon risultato di queste forme di loop è che semplifica l'individuazione e l'implementazione degli stati nei loop. Ad esempio, un ordinamento a bolle si sposta continuamente su un intero array, scambiando valori fuori posto quando li trova. Tiene traccia se un passaggio sull'array ha prodotto scambi. In caso contrario, ogni valore deve trovarsi nel posto giusto, quindi l'ordinamento può terminare. Come ottimizzazione, ad ogni passaggio attraverso l'array, l'ultimo valore dell'array finisce ordinato nella posizione corretta. Quindi, il ciclo può essere ridotto di uno ogni volta. La maggior parte degli algoritmi verifica lo scambio e aggiorna un "bModified" bandiera ogni volta che ce n'è uno. Tuttavia, una volta effettuato il primo scambio, non è necessario per quel compito; è già impostato su true!
Ecco il codice F # che implementa un ordinamento a bolle (sì, l'ordinamento a bolle è un algoritmo terribile; rocce quicksort). Alla fine è un'implementazione imperativa che non cambia stato; aggiorna il flag bModified per ogni scambio. È interessante notare che la soluzione imperativa è più veloce su array di piccole dimensioni e solo uno o due percento più lenta su array di grandi dimensioni. (Fatto per un buon esempio, però).
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
Altri suggerimenti
Oh, ora questa è una domanda intelligente. Eccone alcuni, code snips in python o qualcosa di simile:
-
per i loop può essere sostituito con iteratori
stripped_list = [line.strip () per la riga in line_list] -
per i loop può essere sostituito con applica o mappa o filtro
mappa (in alto, ['frase', 'frammento']) ['SENTENCE', 'FRAGMENT']
-
nidificato per loop con composizione di funzioni
-
ricorsione della coda al posto dei cappi
-
espressioni del generatore al posto di for loop
sum (x * x per x nell'intervallo (10))
Vecchia domanda per i compiti:
La funzione
(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)))
è in tipico stile imperativo, con assegnazione e loop. Scrivi una funzione equivalente f-funzionale che non utilizza le funzioni imperative inizia (sequenza), mentre (vai a) e imposta (assegnazione). Puoi utilizzare tutte le `` funzioni di supporto '' che desideri, purché siano definite usando let o letrec e non al livello più alto.
Una soluzione:
; 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.
Il fold è una funzione molto interessante, che è centrale in molti algoritmi funzionali. Diciamo che vogliamo aggiungere tutti gli elementi di un elenco. Nel codice procedurale, generalmente si crea una variabile accumulatore e la si imposta su 0, quindi si scorre l'elenco e si aumenta l'accumulatore per l'elemento.
In Ocaml, esegui la stessa azione in modo funzionale usando fold:
List.fold_left (+) 0 [1; 2; 3];;
- : int = 6
Usando fold, puoi ad esempio contare il numero di parole nell'elenco e concatenarle contemporaneamente:
List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")
Un altro utile utilizzo di fold è copiare un vettore in un set. Poiché i set in Ocaml sono immutabili, devi effettivamente creare per ogni elemento dell'elenco un nuovo set che contiene il set precedente più quel nuovo elemento.
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]
Qui, il nostro oggetto iniziale è un set vuoto, e ad ogni chiamata, viene creato un nuovo set, basato sul set precedente e sull'elemento corrente usando IntSet.add.
Implementa una volta ricorsivamente te stesso, per sapere come viene eseguito sotto il cofano, quindi utilizza la versione integrata ovunque. Anche in C ++, con std :: accumulate !
Il progetto PLEAC ha quasi esattamente questo come obiettivo: implementare tutti gli esempi nel libro di cucina Perl in altre lingue. Ecco i collegamenti alla versione ocaml (che è una delle tre complete al 100%) http: / /pleac.sourceforge.net/pleac_ocaml/index.html
