Liste des extraits de code fonctionnel pour les programmeurs procéduraux?

Question

Parfois, je reste coincé en essayant de traduire le code procédural en code fonctionnel.

Existe-t-il une liste d'idiomes/extraits fonctionnels mappés à des idiomes/extraits de procédure?

Modifier

Comme il ne semble pas être un site centralisé de ces extraits, je tournais cela dans un wiki communautaire. Veuillez coller les extraits de procédure -> fonctionnels ici.

Answer 1

(Sous la direction de this post sur fshub)

La première fois que je suis allé à atteindre pour la pause/continuer à OCaml/F #, il m'a jeté un (infini) boucle, pour ainsi dire, parce qu'une telle chose n'existe pas! Dans OCaml, on peut utiliser des exceptions pour rompre avec une boucle car elles sont très pas cher, mais en F # (en.NET) le temps système est assez élevé et n'est pas utile pour le contrôle de flux "normal". Ceci est apparu lorsque l'on jouait avec des algorithmes de tri il y a un certain temps (pour tuer un peu de temps), ce qui fait un usage intensif de repeat/until et break. Il m'a frappé que les fonctions d'appel de queue récursives peuvent atteindre exactement le même résultat, avec seulement un léger ding à la lisibilité. Donc, j'ai jeté «bDone mutable» et «tandis que pas bDone» et essayé d'écrire le code sans ces constructions impératives. Ce qui suit distille juste les parties en boucle et montre comment écrire le code de style repeat/until, do/while, while/do, break/continue et test-in-the-middle en utilisant des tailcalls. Tout semble fonctionner exactement à la même vitesse qu'une instruction traditionnelle F # 'while', mais votre kilométrage peut varier (certaines plates-formes peuvent ne pas implémenter correctement le tailcall et donc empiler les erreurs jusqu'à ce qu'elles soient corrigées). A la fin est un algorithme de tri (mauvais) écrit dans les deux styles, à titre de comparaison. Commençons par une boucle 'do/while', écrite en style impératif F # traditionnel, puis examinons les variations fonctionnelles qui fournissent à la fois le même type de boucle, ainsi que différentes sémantiques comme while/do, repeat/until, tester 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 facile. Gardez à l'esprit que f() est toujours appelé au moins une fois (do/while).

Voici le même code, mais dans un style fonctionnel. Notez que nous n'avons pas besoin 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 faire tourner cela à un do/while traditionnel en mettant l'appel de fonction dans le bloc if. Comment répéter un bloc jusqu'à ce que certaines conditions soient vraies (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 

Ce qui était que sur une pause monade moins? Eh bien, introduire 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() 

Que diriez-vous continuer? Eh bien, c'est juste un autre appel à la boucle! Tout d'abord, avec une béquille de syntaxe:

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 puis encore une fois sans (laid) syntaxe Béquille:

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 bon résultat 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, un tri à bulles boucle continuellement sur un tableau entier, en échangeant des valeurs qui ne sont pas à leur place au moment où il les trouve. Il garde la trace de savoir si un passage sur le tableau a produit des échanges. Si non, alors chaque valeur doit être au bon endroit, de sorte que le tri peut se terminer. En tant qu'optimisation, à chaque passage dans le tableau, la dernière valeur du tableau finit par être triée au bon endroit. Ainsi, la boucle peut être raccourcie d'un à chaque fois. La plupart des algorithmes vérifient un swap et mettent à jour un drapeau "bModified" 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é à vrai!

Voici le code F # qui implémente un tri à bulles (oui, le tri à bulles est un algorithme redoutable, les roches quicksort). À la fin est une mise en œuvre impérative qui ne change pas d'état; il met à jour le drapeau bModified pour chaque échange.Fait intéressant, la solution impérative est plus rapide sur les réseaux minuscules et seulement un pour cent ou deux plus lent sur les grands. (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 

Answer 2

Oh, maintenant c'est une question géniale. Voici quelques-unes, code snips in python ou quelque chose Cloe:

• pour les boucles peuvent être remplacées par itérateurs

  stripped_list = [line.strip() for line in line_list]

• pour les boucles peuvent être remplacées par appliquer ou carte ou filtrer

  carte (supérieure, ['phrase', 'fragment']) [ 'PHRASE', 'FRAGMENT']

• imbriqués pour les boucles de composition des fonctions

• de récursion arrière en place des boucles

• expressions du générateur à la place de pour boucles

  sum(x*x for x in range(10))

Answer 3

question Ancien 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 impératif typique, avec affectation et en boucle. Ecrit une fonction équivalente f-fonctionnelle qui n'utilise pas les fonctions impératives begin (séquençage), while (goto), et set (affectation). Vous pouvez utiliser autant de «fonctions auxiliaires» 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. 

Answer 4

Le pli est une fonction très intéressante, qui est centrale dans de nombreux algorithmes fonctionnels. Disons que nous voulons ajouter tous les éléments d'une liste. Dans le code de procédure, vous créez généralement une variable d'accumulateur et la définissez sur 0, puis parcourez la liste et incrémentez l'accumulateur par l'élément.

OCaml, vous effectuez la même action d'une manière fonctionnelle en utilisant pli:

List.fold_left (+) 0 [1; 2; 3];; 
- : int = 6 

fois en utilisant, vous pouvez par exemple compter le nombre de mots dans 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 l'ensemble précédent plus 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, est créé un nouvel ensemble, basé sur le précédent et l'élément en cours en utilisant IntSet.add.

Appliquez le pli récursivement vous-même une fois, pour savoir comment cela se fait sous le capot, puis utilisez la version intégrée partout. Même en C++, avec std::accumulate!

Answer 5

Le projet PLEAC a presque exactement cet objectif: implémenter tous les exemples du livre de recettes perl dans d'autres langues. Voici les liens vers la version d'ocaml (qui est l'un des trois complets à 100%) http://pleac.sourceforge.net/pleac_ocaml/index.html