Programmation Fonctionnelle, TD9

Htmligure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD9 : Boucles fonctionnelles.

Guyslain Naves

Exercice 1 : des boucles fonctionnelles.

On se propose de créer un mécanisme pour faire des boucles façon while ou for tout en restant pûrement fonctionnel : sans assignation.

Pour cela nous proposons la fonction suivante :

  1. let rec repeat init ~f =
  2. match f init with
  3. | `Loop next -> repeat ~f next
  4. | `Stop result -> result

  1. Évaluez l'expression suivante :

    1. let collatz =
    2. repeat 10 ~f:(function
    3. | 1 -> `Stop ()
    4. | n when n mod 2 = 0 -> `Continue (n/2)
    5. | n -> `Continue (3 * n + 1)
    6. )
  2. Utilisez repeat pour afficher tous les caractères d'une chaîne jusqu'à la première espace (utilisez print_char : char -> unit).
  3. Créez une fonction for_loop en utilisant repeat. Elle prend en argument les deux bornes, une fonction et une valeur initiale.
  4. Utilisez for_loop pour écrire la fonction factorielle.

Exercice 2 : yield.

Divers langages de programmation proposent des générateurs, permettant d'énumérer des valeurs en les générant une par une, en se basant sur un mot-clé tel que yield. Un yield ressemble à un return sauf que l'appelant peut ensuite revenir dans la fonction au point juste après le yield. On utilise ensuite une boucle pour traiter toutes les valeurs ainsi générables. Par exemple, on peut écrire en Python :

  1. # from Wikipedia

  3. def countfrom(n):
  4. while True:
  5. yield n
  6. n += 1

  8. for i in countfrom(10):
  9. if i <= 20:
  10. print(i)
  11. else:
  12. break

Cela permet notamment de définir facilement des itérables (comparativement à Java par exemple, essayez de définir un itérateur de nœud d'un arbre par exemple).

La façon naturelle de faire en OCaml est d'utiliser une liste paresseuse. Voici une autre méthode. On définit le module :

  1. module Yield :
  2. sig
  3. type ('value,'response,'final) t =
  4. [ `Done of 'final
  5. | `Yield of 'value * ('response -> ('value, 'response, 'final) t)
  6. ]

  8. val (>>=) :
  9. ('value,'response,'arg) t ->
  10. ('arg -> ('value,'response,'final) t) ->
  11. ('value,'response,'final) t

  13. val return : 'final -> ('value,'response,'final) t

  15. val yield :
  16. 'value ->
  17. ('response -> ('value,'response,'final) t) ->
  18. ('value,'response,'final) t

  20. val iterate :
  21. ('elt,'response,'final) t ->
  22. ('elt -> [ `Stop of 'final | `Continue of 'response]) ->
  23. 'final
  24. end =
  25. struct
  26. type ('value,'response, 'final) t =
  27. [ `Done of 'final
  28. | `Yield of 'value * ('response -> ('value, 'response, 'final) t)
  29. ]

  31. let rec (>>=) yielder fct =
  32. match yielder with
  33. | `Done res -> fct res
  34. | `Yield (value, of_response) ->
  35. `Yield (value, fun response -> of_response response >>= fct)

  37. let return res = `Done res

  39. let yield elt next = `Yield (elt,next)

  41. let rec do_next next fct = function
  42. | `Stop result -> result
  43. | `Continue response -> iterate (next response) fct

  45. and iterate yielder fct =
  46. match yielder with
  47. | `Done result -> result
  48. | `Yield (elt, next) -> do_next next fct (fct elt)
  49. end

Voici la version OCaml du code Python :

  1. open Yield

  3. let rec count_from n =
  4. yield n @@ fun () ->
  5. count_from (n+1)

  7. let _ =
  8. iterate (count_from 10) @@ fun i ->
  9. if i < 20 then `Continue (Printf.printf "%d\n%!" i)
  10. else `Stop ()

  1. Quels sont les rôles de chacun des 3 paramêtres du types Yield.t ?

  2. Écrivez un itérateur des éléments d'une liste :

    1. val list_iterator : 'elt list -> ('elt, unit, unit) Yield.t

  3. Utiliser cet itérateur pour écrire une fonction calculant la somme des éléments d'une liste.

  4. Écrivez un itérateur des nœuds d'un arbre binaire :

    1. val tree_iterator : 'a bin_tree -> ('a, unit, unit) Yield.t

  5. Cette version permet à l'utilisateur de l'itérateur de retourner des valeurs au générateur : la communication se passe dans les deux sens. On peut en profiter, par exemple pour faire un algorithme de recherche d'une clé dans un arbre binaire de recherche. Créez les deux fonctions suivantes :

    1. val descent_tree :
    2. 'elt bin_tree -> ('elt, [< `Left | `Right | `This ], 'elt bin_tree) Yield.t
    3. val find_key : 'elt -> 'elt bin_tree -> 'elt bin_tree = <fun>

    find_key retourne le sous-arbre ayant l'élément cherché pour racine, ou une feuille.