Liste d'extraits de code fonctionnel pour les programmeurs procéduraux? [fermé]
https://stackoverflow.com/questions/832569
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Parfois, je suis toujours bloqué pour essayer de traduire le code de procédure en code fonctionnel.
Existe-t-il une liste des idiomes / extraits fonctionnels mappés aux idiomes / extraits de procédure?
Modifier
Comme il ne semble pas exister de site Web centralisé contenant ces extraits, je suis en train de le transformer en un wiki de communauté. Veuillez coller toute procédure - > extraits fonctionnels ici.
La solution
(Édité de cette publication sur fshub )
La première fois que je suis allé chercher une pause / une poursuite dans OCaml / F #, cela m’a jeté pour une boucle (infinie), pour ainsi dire, car aucune telle chose n’existe! Dans OCaml, vous pouvez utiliser des exceptions pour rompre une boucle car elles sont très pas chères, mais en F # (en .NET), la surcharge est assez lourde et inutile pour "normal". contrôle de flux.
Cela est arrivé lorsqu’on jouait avec des algorithmes de tri il ya quelque temps (pour tuer un peu de temps), qui font un usage intensif de repeat / Until et break. Je me suis rendu compte que les fonctions d’appel de queue récursives peuvent produire exactement le même résultat, avec seulement une légère perte de lisibilité. J'ai donc jeté 'mutable bDone' et 'tant que je ne suis pas bDone' et j'ai essayé d'écrire le code sans ces constructions impératives. Ce qui suit résume uniquement les parties en boucle et montre comment écrire le code de style test-in-the-middle à l'aide des appels successifs. Celles-ci semblent toutes fonctionner à la même vitesse qu'une déclaration traditionnelle "# while", mais votre kilométrage peut varier (certaines plates-formes peuvent ne pas implémenter correctement l'appel final et peuvent donc empiler les erreurs jusqu'à ce qu'elles soient corrigées). À la fin se trouve un (mauvais) algorithme de tri écrit dans les deux styles, à des fins de comparaison.
Commençons par une boucle 'do / while', écrite dans le style impératif traditionnel F #, puis examinons les variations fonctionnelles qui fournissent à la fois le même type de boucle, ainsi que différentes sémantiques telles que while / do, repeat / Until, test au milieu, et même casser / continuer (sans monades .. euh, 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, c'est assez simple. N'oubliez pas que f () est toujours appelé au moins une fois (do / while).
Voici le même code, mais dans un style fonctionnel. Notez qu'il n'est pas nécessaire de déclarer un mutable ici.
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
Nous pouvons appliquer cela à un do / while traditionnel en plaçant l'appel de fonction à l'intérieur du bloc if.
let funWhileDo() =
let rec loop x =
if x < N then (*While*)
f() (*Do*)
loop (x+1)
loop 0
Pourquoi ne pas répéter un bloc jusqu'à ce qu'une condition soit vraie (répéter / jusqu'à)? Assez facile ...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then () (*Until*)
else loop (x+1)
loop 0
Qu'en était-il d'une pause sans monade? Eh bien, introduisez simplement une expression conditionnelle qui renvoie "unité", comme dans:
let funBreak() =
let rec loop() =
let x = g()
if x > N then () (*break*)
else
f()
loop()
loop()
Pourquoi ne pas continuer? Eh bien, ce n'est qu'un autre appel à faire une boucle! Tout d'abord, avec une syntaxe béquille:
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'()
Et encore une fois sans la (laide) béquille de la syntaxe:
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 comme bonjour!
Un des résultats intéressants de ces formes de boucle est qu’il est plus facile de repérer et d’implémenter des états dans vos boucles. Par exemple, une sorte de bulle boucle continuellement sur un tableau entier, échangeant des valeurs qui ne sont pas à sa place. Il enregistre si un passage sur le tableau a généré des échanges. Sinon, chaque valeur doit être au bon endroit pour que le tri puisse se terminer. Comme optimisation, à chaque passage dans le tableau, la dernière valeur du tableau est triée au bon endroit. Ainsi, la boucle peut être raccourcie de un à chaque fois. La plupart des algorithmes recherchent un échange et mettent à jour un fichier "bModified". drapeau chaque fois qu'il y en a un. Cependant, une fois le premier échange effectué, cette affectation n’est plus nécessaire; c'est déjà réglé sur true!
Voici le code F # qui implémente une sorte de bulle (oui, la sorte de bulle est un algorithme terrible; les pierres de tri rapide). Au final se trouve une mise en œuvre impérative qui ne change pas d'état; il met à jour l'indicateur bModified pour chaque échange. Il est intéressant de noter que la solution impérative est plus rapide sur les matrices minuscules et à peine un ou deux pour cent plus lente sur les grandes. (Fait pour un bon exemple, cependant).
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
Autres conseils
Oh, maintenant c'est une bonne question. En voici quelques-uns, du code piraté en python ou quelque chose de différent:
-
pour les boucles peuvent être remplacés par des itérateurs
stripped_list = [line.strip () pour line dans line_list] -
pour les boucles peuvent être remplacées par apply ou map ou filter
map (upper, ['phrase', 'fragment']) ['SENTENCE', 'FRAGMENT']
-
imbriqué pour les boucles avec composition de fonctions
-
récursion de queue à la place des boucles
-
expressions génératrices à la place des boucles for
sum (x * x pour x dans l'intervalle (10))
Ancienne question sur les devoirs:
La fonction
(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)))
est dans un style typique impératif, avec assignation et boucle. Ecrivez une fonction f-fonctionnelle équivalente qui n'utilise pas les fonctions impératives début (séquence), tant que (goto), et définie (affectation). Vous pouvez utiliser autant de "fonctions d'assistance" que vous le souhaitez, à condition qu'elles soient définies à l'aide de let ou letrec et non au niveau supérieur.
Une solution:
; 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.
Le fold est une fonction très intéressante, centrale dans de nombreux algorithmes fonctionnels. Disons que nous voulons ajouter tous les éléments d'une liste. En code de procédure, vous devez généralement créer une variable d'accumulateur et la définir sur 0, puis parcourir la liste et incrémenter l'accumulateur de l'élément.
Dans Ocaml, vous effectuez la même action de manière fonctionnelle en utilisant fold:
List.fold_left (+) 0 [1; 2; 3];;
- : int = 6
En utilisant fold, vous pouvez par exemple compter le nombre de mots de la liste et les concaténer en même temps:
List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")
Une autre utilisation utile de fold est de copier un vecteur dans un ensemble. Comme les ensembles dans Ocaml sont immuables, vous devez créer pour chaque élément de la liste un nouvel ensemble contenant le jeu précédent et ce nouvel élément.
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]
Ici, notre objet initial est un ensemble vide et, à chaque appel, un nouvel ensemble est créé, en fonction de l'ensemble précédent et de l'élément actuel à l'aide de IntSet.add.
Implémentez vous-même une fois récursivement une fois, pour savoir comment cela se passe sous le capot, puis utilisez la version intégrée partout. Même en C ++, avec std :: accumulate !
Le projet PLEAC a presque exactement cela pour objectif: implémenter tous les exemples du livre de recettes perl dans d'autres langues. Voici les liens vers la version ocaml (qui est l’un des trois complets à 100%) http: / /pleac.sourceforge.net/pleac_ocaml/index.html
