D'après ce que j'ai pu glâner comme infos sur le net, en lisant notamment ce papier ( www.cs.nott.ac.uk/~gmh/fold.pdf ) assez théorique, j'en ai déduit ceci : "Tout algorithme récursif terminal (tail-recursive) sur une liste peut être exprimé avec un fold (*). De même qu'on ne peut exprimer avec un fold QUE des algos recursifs terminaux".
Question 1: Est-ce que quelqu'un confirme ce postulat, ou bien est-ce que je me plante lourdement ?
Deuxièmement, pour étayer cet axiome, j'ai codé ma fonction zip moi même (comme un grand):
No problem, sauf que bien entendu elle n'est pas récursive terminale. Donc, elle ne serait pas exprimable avec un fold, ce à quoi d'ailleurs je ne suis pas parvenu.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 zip' (x:xs) (y:ys) = (x,y):(zip' xs ys) zip' _ _ = []
Question 2: Quelqu'un a-t-il un algo de zip qui soit terminal ou bien codé avec un fold ?
(*) foldr pours les grands, foldl pour les glands. Ok, stop the troll.
Partager