• [^] # Re: Exemple judicieux ?

    Posté par . En réponse à la dépêche Apprendre la programmation fonctionnelle avec le MOOC OCaml. Évalué à 2.

    Version courte: votre "fold" ne fait pas la même chose

    C'est là qu'est l'erreur, cette fonction fait exactement la même chose !

    Que fait un fold sur une liste ?

    1. Il commence avec une graine : le paramètre f dans le code du journal
    2. Il accumule des valeurs : le paramètre g dans le code du journal

    Une preuve possible que c'est bien la même chose, nous allons montrer que si f et e sont respectivement une fonction d'accumulation et une graine, alors on peut trouver f' et g' deux fonctions (arguments du fold du journal) telles que quelque soit la liste l : 

    fold f e l = fold f' g' (encode_en_arbre l)

    J'ai commencé une preuve sur la structure du journal, mais celle-ci possède de nombreux défauts

    1. Les arbres ne contiennent que des entiers
    2. Il n'y a pas d'arbre vide

    Le deuxième point ne permet pas d'encoder la liste vide, le premier est plus embêtant parce qu'il ne permet pas de retrouver où commence la liste dans l'encodage (tous les noeuds sont identiques).