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. Utilisez repeat pour afficher tous les caractères d'une chaîne jusqu'à la première espace.
  2. Créez une fonction for_loop en utilisant repeat. Elle prend en argument les deux bornes, une fonction et une valeur initiale.
  3. Utilisez for_loop pour écrire la fonction factorielle.

Exercice 2 : monade d'état.

Voici l'interface d'une monade d'état :

  1. type state
  2. type 'value t = state -> 'value * state

  4. val (>>=) : 'value t -> ('value -> 'result t) -> 'result t
  5. val (>>) : 'unit t -> 'result t -> 'result t
  6. val return : 'value -> 'value t

  8. val set : state -> unit t
  9. val get : state t

Il faut comprendre que 'value t est une action produisant une valeur de type 'value. Par ailleurs, cette action a accès à un état qu'elle peut lire ou écrire.

On suppose disposer d'une monade d'état dont le type stateest int.

  1. Définissez l'action print_state : unit t affichant la valeur de l'état.
  2. Définissez l'action incr : unit t augmentant de 1 la valeur de l'état.
  3. Définissez une suite d'actions, consistant à incrémenter deux fois le compteur, l'afficher, l'incrémenter une fois et l'afficher de nouveau.
  4. Soit une fonction apply : int -> unit t. On souhaite créer l'action consistant à faire successivement apply ipour i valant de lower à upper. Définissez une telle boucle for.

  5. Écrivez l'action permettant de calculer la factorielle d'un entier $n$ à l'aide de la question précédente. Vous pouvez modifier l'état arbitrairement.

    1. val fact : int -> int t
  6. Créez une implémentation des monades d'état.

Exercice 3 : 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 las valeurs ainsi générable. 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éreur 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 (>>) :
  14. ('value,'response,unit) t ->
  15. ('value,'response,'final) t ->
  16. ('value,'response,'final) t

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

  20. val yield :
  21. 'value ->
  22. ('response -> ('value,'response,'final) t) ->
  23. ('value,'response,'final) t

  25. val iterate :
  26. ('elt,'response,'final) t ->
  27. ('elt -> [ `Stop of 'final | `Continue of 'response]) ->
  28. 'final
  29. end =
  30. struct
  31. type ('value,'response, 'final) t =
  32. [ `Done of 'final
  33. | `Yield of 'value * ('response -> ('value, 'response, 'final) t)
  34. ]

  36. let rec (>>=) yielder fct =
  37. match yielder with
  38. | `Done res -> fct res
  39. | `Yield (value, of_response) ->
  40. `Yield (value, fun response -> of_response response >>= fct)

  42. let (>>) yielder1 yielder2 = yielder1 >>= fun () -> yielder2

  44. let return res = `Done res

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

  48. let rec do_next next fct = function
  49. | `Stop result -> result
  50. | `Continue response -> iterate (next response) fct

  52. and iterate yielder fct =
  53. match yielder with
  54. | `Done result -> result
  55. | `Yield (elt, next) -> do_next next fct (fct elt)
  56. 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. Écrivez un itérateur des éléments d'une liste :

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

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

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

  3. 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.