Callcc/Guyslain/Teaching/ProgFonc/TP2018/TD9

Version & licenses
Creative Commons License
  1. {`author "Guyslain Naves"}
  2. {`date "Janvier 2015"}
  3. {`windowtitle "Programmation Fonctionnelle, TD9"}
  4. {`frametitle "Programmation Fonctionnelle, TD9 : Boucles fonctionnelles."}
  5. {`menu "progfonc"}
  6. {`leftpicture af://guyslain/images/Teaching/ProgFonc/OCaml_Sticker.svg}



  7. {section 3 Exercice 1 : des boucles fonctionnelles.}

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

  11. Pour cela nous proposons la fonction suivante :

  12. {code {`language "ocaml"} {:
  13. let rec repeat init ~f =
  14. match f init with
  15. | `Loop next -> repeat ~f next
  16. | `Stop result -> result
  17. :}}

  18. + {subframe Évaluez l'expression suivante :
  19. {code {`language "ocaml"} {:
  20. let collatz =
  21. repeat 10 ~f:(function
  22. | 1 -> `Stop ()
  23. | n when n mod 2 = 0 -> `Continue (n/2)
  24. | n -> `Continue (3 * n + 1)
  25. )
  26. :}}
  27. }
  28. + Utilisez {verb {:repeat:}} pour afficher tous les caractères d'une
  29. chaîne jusqu'à la première espace (utilisez
  30. {verb {:print_char : char -> unit:}}).
  31. + Créez une fonction {verb {:for_loop:}} en utilisant {verb
  32. {:repeat:}}. Elle prend en argument les deux bornes, une fonction et
  33. une valeur initiale.
  34. + Utilisez {verb {:for_loop:}} pour écrire la fonction factorielle.


  35. {section 3 Exercice 2 : yield.}

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

  43. {code {:
  44. # from Wikipedia

  45. def countfrom(n):
  46. while True:
  47. yield n
  48. n += 1

  49. for i in countfrom(10):
  50. if i <= 20:
  51. print(i)
  52. else:
  53. break
  54. :}}

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

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

  60. {code {`language "ocaml"} {:
  61. module Yield :
  62. sig
  63. type ('value,'response,'final) t =
  64. [ `Done of 'final
  65. | `Yield of 'value * ('response -> ('value, 'response, 'final) t)
  66. ]

  67. val (>>=) :
  68. ('value,'response,'arg) t ->
  69. ('arg -> ('value,'response,'final) t) ->
  70. ('value,'response,'final) t

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

  72. val yield :
  73. 'value ->
  74. ('response -> ('value,'response,'final) t) ->
  75. ('value,'response,'final) t

  76. val iterate :
  77. ('elt,'response,'final) t ->
  78. ('elt -> [ `Stop of 'final | `Continue of 'response]) ->
  79. 'final
  80. end =
  81. struct
  82. type ('value,'response, 'final) t =
  83. [ `Done of 'final
  84. | `Yield of 'value * ('response -> ('value, 'response, 'final) t)
  85. ]

  86. let rec (>>=) yielder fct =
  87. match yielder with
  88. | `Done res -> fct res
  89. | `Yield (value, of_response) ->
  90. `Yield (value, fun response -> of_response response >>= fct)

  91. let return res = `Done res

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

  93. let rec do_next next fct = function
  94. | `Stop result -> result
  95. | `Continue response -> iterate (next response) fct

  96. and iterate yielder fct =
  97. match yielder with
  98. | `Done result -> result
  99. | `Yield (elt, next) -> do_next next fct (fct elt)
  100. end
  101. :}}

  102. Voici la version OCaml du code Python :
  103. {code {`language "Ocaml"} {:
  104. open Yield

  105. let rec count_from n =
  106. yield n @@ fun () ->
  107. count_from (n+1)

  108. let _ =
  109. iterate (count_from 10) @@ fun i ->
  110. if i < 20 then `Continue (Printf.printf "%d\n%!" i)
  111. else `Stop ()
  112. :}}

  113. + {subframe Quels sont les rôles de chacun des 3 paramêtres du types
  114. {verb {:Yield.t:}} ?}
  115. + {subframe Écrivez un itérateur des éléments d'une liste :
  116. {code {`language "ocaml"} {:
  117. val list_iterator : 'elt list -> ('elt, unit, unit) Yield.t
  118. :}}}
  119. + {subframe Utiliser cet itérateur pour écrire une fonction calculant
  120. la somme des éléments d'une liste.}
  121. + {subframe Écrivez un itérateur des nœuds d'un arbre binaire :
  122. {code {`language "ocaml"} {:
  123. val tree_iterator : 'a bin_tree -> ('a, unit, unit) Yield.t
  124. :}}}
  125. + {subframe Cette version permet à l'utilisateur de l'itérateur de
  126. retourner des valeurs au générateur : la communication se passe dans
  127. les deux sens. On peut en profiter, par exemple pour faire un
  128. algorithme de recherche d'une clé dans un arbre binaire de recherche.
  129. Créez les deux fonctions suivantes :
  130. {code {`language "ocaml"} {:
  131. val descent_tree :
  132. 'elt bin_tree -> ('elt, [< `Left | `Right | `This ], 'elt bin_tree) Yield.t
  133. val find_key : 'elt -> 'elt bin_tree -> 'elt bin_tree = <fun>
  134. :}}
  135. {verb {:find_key:}} retourne le sous-arbre ayant l'élément cherché pour racine,
  136. ou une feuille.
  137. }