• [^] # Re: Programmation Dynamique

    Posté par . En réponse au journal Haskell -- Évaluation paresseuse. Évalué à 1.

    D'autant que sur un tel code, la définition de la fonction suit le schéma de la preuve par récurrence qui justifie son bon fonctionnement (c'est le principe même des langages fonctionnels, et des structures récursives).

    Exemple en OCaml sur le calcul de la hauteur d'un arbre binaire :

    type 'a btree = Empty | Btree of'a tree * a * 'a tree
let rec depth t = 
 match t with
 (* arbre vide, ou preuve de P(0) i.e on initialise la récurrence *)
 | Empty -> 0
 (* arbre à deux branches, ou preuve de P(n) => P(n+1) *)
 | Btree(left, _, right) -> (max_int (depth left) (depth right)) + 1
depth (Btree(Empty, 1, Btree(Empty, 0, Empty)))
- : int = 2

    Dans ton cas, c'était une récurrence double et à la lecture du code il n'est pas difficile de se convaincre qu'il est correct. Sur des cas plus complexes, cela demande plus de réflexion, mais en fonctionnel cela reste plus simple.

    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.