Discussion :

[limestrael]

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):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
zip' (x:xs) (y:ys) = (x,y):(zip' xs ys)
zip' _ _ = []

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.
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.

[alex_pi]

On me demande de te faire part de cette solution :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
zip' xs ys = reverse · fst · foldr f ([],ys) · reverse $ xs
     where f _ r@(_, [])  = r
           f x (rs, z:zs) = ((x,z):rs)

[SpiceGuid]

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.

À mon avis on parle de tous les algos qui s'éxécutent en un temps fini, pas seulement des algos où la récursion est terminale.

Question 1: Est-ce que quelqu'un confirme ce postulat, ou bien est-ce que je me plante lourdement ?

• à chaque constructeur initial (nil) le fold associe une constante.
• à chaque constructeur composite (cons) le fold associe une application de fonction

En clair ça veut dire que le fold construit une expression qui ressemble en tous points au TAD sur lequel il est appliqué.
Dit autrement, le fold est un foncteur de l'algèbre initiale vers la F-algèbre (à cet égard la syntaxe de Coq pour les types inductifs et bien plus explicite que celle de Caml/Haskell).

• les types inductifs définissent des TAD finis pour lesquels un fold ne peut donner lieu qu'à des expressions dont l'évaluation se termine
• de façon duale les types coinductifs définissent des TAD éventuellement infinis pour lesquels des unfold donnent lieu à des expressions dont l'évaluation éventuellement ne se termine pas

Une autre façon de voir c'est de dire que l'application est un destructeur pour les types fonctionnels et que le (un-)fold est un destructeur pour les types (co-)inductifs. C'est la façon de voir d'Alain Prouté et des langages d'inspiration catégorique en général (voir http://www.developpez.net/forums/d67...fonctionnelle/).
Le gros problème pratique c'est que pour faire de la récursion mutuelle tu es obligé d'utiliser des astuces comparables à simuler un let rec à partir du let. Même chose si tu veux parcourir deux TAD simultanément, par exemple pour fusionner deux listes triées.
Selon moi le fold n'est pas une récursion de plus haut niveau mais au contraire un assembleur de récursion, à la manière du lambda-calcul qui est un assembleur de langages fonctionnels.

[limestrael]

On me demande de te faire part de cette solution :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
zip' xs ys = reverse · fst · foldr f ([],ys) · reverse $ xs
     where f _ r@(_, [])  = r
           f x (rs, z:zs) = ((x,z):rs)

Effectivement, je n'avais pas pensé à mettre la seconde liste dans l'accumulateur (le zéro). Mais je pense qu'il y a une erreur.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
zip' xs ys = reverse . fst . foldr f ([], ys) . reverse $ xs
    where f _ r@(_,  []) = r
          f x (rs, z:zs) = ((x,z):rs, zs)

Mais c'est vrai que là, par contre, à cause des reverses ça serait plus simple à faire avec un foldl.


@SpiceGuid : Je suis d'accord.
Non, en fait, tu as sûrement répondu à ma question mais d'une façon trop compliquée. Je parle juste d'algorithmie pure, de conversion algo récursif <--> fold.

J'ai l'impression que tu me dis qu'en fonction du type qu'on utilise (puisqu'un fold, dans la théorie, peut être appliqué à autre chose qu'une liste) un fold peut ou non être terminal.

En clair ça veut dire que le fold construit une expression qui ressemble en tous points au TAD sur lequel il est appliqué.

Ca, j'ai compris.

Dit autrement, le fold est un foncteur de l'algèbre initiale vers la F-algèbre

A t'entendre, on dirait qu'il faut avoir pigé toute la théorie des catégories pour pouvoir faire du haskell. J'ai que très peu étudié les foncteurs, , je comprends plus ou moins ce que tu veux dire, mais explicite juste ce que tu entends par les catégories "algèbre initiale" et "F-algèbre" (Je dis "catégories", d'après la définition d'un foncteur, enfin celle de wiki).
Je ne vois d'ailleurs pas trop non plus le rapport entre les foncteurs (en math) et les foncteurs en haskell, qui sont, d'après ce que j'ai vu, des structures "mappables" (fmap f (Maybe x) = Maybe (f x)) et non des applications. (*)

(*) EDIT: Ok, en fait je crois que j'ai compris: (je réponds à ma propre question, en fait)
On a par exemple 2 catégories, les a et les peut-être-un-a (Maybe a). Le type Maybe définit deux constructeurs de données: Just et Nothing. Ce sont en Haskell des fonctions, qui permettent de passer de la catégorie a à la catégorie Maybe a.
Un foncteur est la donnée de deux choses:
- Une fonction F, qui permet de passer d'une catégorie C (les a) dans une catégorie D (les Maybe a)
- Une fonction G, qui permet de transformer un morphisme de C (une application a -> b) en un morphisme de D (une application Maybe a -> Maybe b)
C'est donc le constructeur de données Just qui est, au sens mathématique, la fonction F, qui comme le stipule la théorie permet de passer d'une catégorie à l'autre tout en conservant les informations (La valeur 'Just x' contient toujours x, l'entier initial, donc Maybe a contient les informations de a tout en en rajoutant). La preuve, on peut continuer à appliquer des homomorphismes a -> b via fmap, qui est la fonction G.
J'ai raison ? J'ai tort ? C'est plus compliqué que ça ?

[SpiceGuid]

A t'entendre, on dirait qu'il faut avoir pigé toute la théorie des catégories pour pouvoir faire du haskell.

Ça n'est pas indispensable pour faire. Mieux vaut soigner ton code. Plus ton code est soigné plus les notions compliquées auront des chances de te paraître familières.

explicite juste ce que tu entends par les catégories "algèbre initiale" et "F-algèbre"

Algèbre initiale: c'est un type récursif somme de produits
F-algèbre: c'est un type récursif somme de fonctions

On prend souvent l'exemple des entiers de Peano parce que c'est un TAD simple et linéaire (similaire aux listes, le polymorphisme en moins) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
(* algèbre initiale *)
type A-nat = zero         (* un constructeur constant *)
           | succ A-nat   (* un constructeur unaire   *)

(* F-algèbre *)
type F-nat = zero: () -> F-nat      (* une fonction constante *)
           | succ: F-nat -> F-nat   (* une fonction unaire    *)

L'opérateur "|" désigne la somme (union disjointe).
Les types A-nat et F-nat sont des catégories bicartésiennes.
Le fold associé est un foncteur de A-nat vers F-nat.
Tu lui dis comment transformer un noeud et il te répond comment transformer toute la structure.

Dans ton exemple Maybe est la structure, l'élément est de type a ou b, et un foncteur est du type
(a -> b) -> (Maybe a -> Maybe b).
Tu lui dis comment transformer l'élément et il te répond comment transformer Maybe.

Question 2: Quelqu'un a-t-il un algo de zip qui soit terminal ou bien codé avec un fold ?

Ce que tu veux, en général, c'est ajouter une liste-argument supplémentaire à ton fold pour obtenir un bifold qui itère sur deux listes (de même longueur) de façon synchronisée.

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let bifold f init l1 l2 =
  List.fold_right
  ( fun a g -> 
     function
     | [] -> init
     | (b::l) -> f a b (g l)
  ) 
  l1
  (fun _ -> init)
  l2

[limestrael]

Je réutilise ce thread pour énoncer un problème qui m'est venu récemment (ça concerne toujours la récursivité terminale).
C'est à propos de l'utilisation d'une monade pour faire transiter un accumulateur. Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
sum [] = 0
sum (x:xs) = 1 + sum xs

n'est pas terminal, mais on peut utiliser la monade Writer et le monoide Sum pour le transformer ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
sum = getSum . execWriter . runWriter sumW
  where
    sumW [] = return ()
    sumW (x:xs) = do
        tell (Sum x)
        sumW xs

Ce n'est pas l'exemple le plus pertinent d'utilisation de la monade Writer, mais c'était pour donner un exemple simple.

Dans ce cas là, on évite le fameux '1+sum xs' qui fait que l'algo initial n'est pas terminal, mais le do-bloc ne trompe pas, on a bien en réalité 'tell (Sum x) >> sumW xs', et donc l'appel récursif n'est pas seul sur sa ligne (il fait partie d'une chaîne de fonctions).
Mais je sais que ghc optimise les utilisations des Monades, du coup, sait-il traiter cet algo comme récursif terminal et l'optimiser comme tel ?

[Jedai]

GHC n'optimise pas les utilisations des monades en particulier, il n'a même pas particulièrement conscience qu'il a affaire à des monades, bien qu'il y ait certaines optimisations générales qui peuvent s'appliquer à du code monadique.

Donc à ta question, je réponds non vu que la monade Writer n'est pas stricte en son "état" sauf si tu utilises une version plus stricte que la standard.

(Il est toujours possible que GHC optimise ta version monadique comme il optimiserait une version avec accumulateur simple si tu utilises -O1 ou -O2)

--
Jedaï

[limestrael]

Donc à ta question, je réponds non vu que la monade Writer n'est pas stricte en son "état" sauf si tu utilises une version plus stricte que la standard.

Ok, donc utiliser cette astuce pour tenter d'obtenir un algo récursif terminal, c'est pas la bonne idée.
Par contre, tu dis qu'avec une monade stricte ce serait terminal ? Je vois pas spécalement le rapport...

[Jedai]

Ok, donc utiliser cette astuce pour tenter d'obtenir un algo récursif terminal, c'est pas la bonne idée.
Par contre, tu dis qu'avec une monade stricte ce serait terminal ? Je vois pas spécalement le rapport...

Ni dans un cas, ni dans l'autre ce ne sera récursif terminal : la récursivité terminale est une propriété du code que tu écris, ça ne fait pas vraiment sens d'aller le chercher dans le résultat d'une optimisation par un compilateur.

Par ailleurs, la récursivité terminale n'est pas vraiment optimisée par un compilateur Haskell... Mais le modèle d'évaluation de GHC par exemple implique qu'une fonction récursive terminale aura certains avantages analogues à ceux d'une fonction récursive terminale dans d'autres langages. Contrairement à d'autres langages, cela ne suffit pas toujours à garantir un bon comportement (cf : sum = go 0 where { go n [] = n; go n (x:xs) = go (n+x) xs }, bien que récursive terminale, l'accumulateur n'est pas strict et peut donc accumuler un thunk qui fera péter la pile quand évalué).

--
Jedaï

[limestrael]

sum = go 0 where { go n [] = n; go n (x: xs) = go (n+x) xs }, bien que récursive terminale, l'accumulateur n'est pas strict et peut donc accumuler un thunk qui fera péter la pile quand évalué

Ouaip, je connais. C'est l'exemple type du cas où il faut y aller à seq (calembour).