Re: [Caml-list] Great Beginner

["Diego Olivier Fernandez Pons" <FernandezPons@iFrance.com>]

Rémi Vanicat a proposé le code suivant :

let rec somme n =
  if n = 0 then 0
  else n + (somme (n - 1))

let somme n =
  let rec aux i x =
    if i <= n then
      aux (i+1) (x + i)
    else x in
  aux 1 0

Ce code reste néanmoins très proche du code impératif. Dans un style
beacoup plus fonctionnel on aura plutôt :

let rec somme = function
  | 0 -> 0
  | k -> k + somme (k-1)
;;

La première ligne s'assure que la récurrence descendante se terminera
correctement, la deuxième définit cette récurrence. On appelle cette
définition par disjonction de cas le « pattern matching » très présent
dans les langages fonctionnels.

L'instruction  #trace somme;;   vous permet de voir les appels
successifs de la fonction

#   somme <-- 3
somme <-- 2
somme <-- 1
somme <-- 0
somme --> 0
somme --> 1
somme --> 3
somme --> 6
- : int = 6

Examinons à présent la fonction récursive terminale (l'idée est
d'envoyer à la fonction en paramètre à la fois le total calculé et le
nombre d'étapes effectuées (ou à effectuer))

let somme1 = function n ->
   let rec sommeCPS = function
     | (total, k) when (k = n + 1) -> total
     | (total, k) -> sommeCPS (total + k, k + 1)
  in
       sommeCPS (0, 0)
;;

le première ligne sert à arrêter la récurrence au bon moment (lorsque
indice est à n+1, autrement dit on vient de calculer la somme des n
premiers termes). La seconde ligne définit cette récurrence. La ligne
sommeCPS (0, 0) indique que l'on commence à compter à partir de
l'indice 0 et que l'on part d'un total de 0.

A vrai dire, je préfère la récurrence descendante, en effet, la
fonction interne sommeCPS n'est plus dépendante de la fonction
extérieure puisqu'elle n'a pas à connaître n

let rec sommeCPS = function
    | (total, k) when (k = 0) -> total
    | (total, k) -> sommeCPS (total + k, k - 1)
;;

On peut à présent définir la fonction somme :

let somme = function n -> somme (0, n)

et la tracer sommeCPS pour voir son fonctionnement

#   val somme : int -> int = <fun>
sommeCPS <-- 0,   5
sommeCPS <-- 5,   4
sommeCPS <-- 9,   3
sommeCPS <-- 12, 2
sommeCPS <-- 14, 1
sommeCPS <-- 15, 0
sommeCPS --> 15

On voit bien l'indice décrémenter tandis que le total augmente.

Bien sûr, vous pouvez toujours définir sommeCPS à l'intérieur de somme
pour ne pas encombrer votre espace de noms (mais alors vous ne pouvez
plus la tracer)

let somme = function n ->
   let rec sommeCPS = function
      | (total, k) when (k = 0) -> total
      | (total, k) -> sommeCPS (total + k, k - 1)
   in
       sommeCPS (0, n)
;;

Enfin, je vous recommande de « commenter » votre code par des noms de
variables explicites (comme total ou k plutôt que aux, acc, etc.) ;
cela permet un code immédiatement compréhensible.

La seule remarque supplémentaire que l'on pourrait faire est que dans
les langages fonctionnels on préfère les fonctions à plusieurs
arguments que les fonctions à arguments dans les produits cartésiens
(ce qui ici n'est guère difficile car vous ne faites aucun test sur la
variable total)

let somme = function n ->
   let rec sommeCPS = function total -> function
      | 0 -> total
      | k -> sommeCPS (total + k)  (k - 1)
   in
       sommeCPS 0 n
;;

        Diego Olivier


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr