Ecriture en utilisant foldr

Dans le monde réel Haskell , Chapitre 4. Programmation fonctionnelle

Écrivez foldl avec foldr:

-- file: ch04/Fold.hs myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl fz xs = foldr step id xs z where step xga = g (fax) 

Le code ci-dessus m’a beaucoup dérouté, et un gars appelé dps l’a réécrit avec un nom significatif pour le rendre plus clair:

 myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL where stepR lastL accR accInitL = accR (stepL accInitL lastL) 

Jef G a ensuite fait un excellent travail en fournissant un exemple et en mettant en évidence le machanisme sous-jacent:

 myFoldl (+) 0 [1, 2, 3] = (foldR step id [1, 2, 3]) 0 = (step 1 (step 2 (step 3 id))) 0 = (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0 = (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0 = (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0 = (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0 = (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0 = (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0 = (+) ((+) ((+) 0 1) 2) 3 = ((0 + 1) + 2) + 3 

Mais je ne peux toujours pas comprendre cela, voici mes questions:

  1. A quoi sert la fonction id? Quel est le rôle de? Pourquoi devrions-nous en avoir besoin ici?
  2. Dans l’exemple ci-dessus, id function est l’accumulateur dans la fonction lambda?
  3. Le prototype de foldr est foldr :: (a -> b -> b) -> b -> [a] -> b , et le premier paramètre est une fonction nécessitant deux parameters, mais la fonction step de l’implémentation myFoldl utilise 3 parameters , Je suis complètement confus!

Est-ce qu’il y a quelqu’un qui peut m’aider? Merci beaucoup!

Quelques explications sont en ordre!

A quoi sert la fonction id? Quel est le rôle de? Pourquoi devrions-nous en avoir besoin ici?

id est la fonction d’identité , id x = x , et est utilisée comme l’équivalent de zéro lors de la constitution d’une chaîne de fonctions avec une composition de fonction , (.) . Vous pouvez le trouver défini dans le prélude .

Dans l’exemple ci-dessus, id function est l’accumulateur dans la fonction lambda?

L’accumulateur est une fonction en cours de construction via l’application de fonction répétée. Il n’y a pas de lambda explicite, puisque nous nommons l’accumulateur, step . Vous pouvez l’écrire avec un lambda si vous voulez:

 foldl fa bs = foldr (\bgx -> g (fxb)) id bs a 

Ou comme Graham Hutton écrirait :


entrer la description de l'image ici


Le prototype de foldr est foldr :: (a -> b -> b) -> b -> [a] -> b

Un programmeur Haskell dirait que le type de foldr est (a -> b -> b) -> b -> [a] -> b .

et le premier paramètre est une fonction qui nécessite deux parameters, mais la fonction step de l’implémentation de myFoldl utilise 3 parameters, je suis complètement confus

C’est déroutant et magique! Nous jouons un tour et remplaçons l’accumulateur par une fonction, qui est à son tour appliquée à la valeur initiale pour obtenir un résultat.

Graham Hutton explique le truc pour transformer foldl en foldr dans l’article ci-dessus. Nous commençons par écrire une définition récursive de foldl :

 foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv [] = v foldl fv (x : xs) = foldl f (fvx) xs 

Et puis refactorez-le via la transformation d’argument statique sur f :

 foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv xs = g xs v where g [] v = v g (x:xs) v = g xs (fvx) 

Réécrivons maintenant g pour faire flotter les v :

 foldl fv xs = g xs v where g [] = \v -> v g (x:xs) = \v -> g xs (fvx) 

Ce qui revient à penser à g en fonction d’un argument qui renvoie une fonction:

 foldl fv xs = g xs v where g [] = id g (x:xs) = \v -> g xs (fvx) 

Maintenant, nous avons g , une fonction qui parcourt récursivement une liste, applique une fonction f . La valeur finale est la fonction d’identité et chaque étape entraîne également une fonction.

Mais , nous avons déjà une fonction récursive très similaire sur les listes, foldr !


entrer la description de l'image ici


Cela ressemble à un schéma récursif très similaire à notre fonction g . Maintenant, l’astuce: en utilisant toute la magie disponible (aka Bird, Meertens et Malcolm), nous appliquons une règle spéciale, la propriété universelle de fold , qui est une équivalence entre deux dé fi nitions pour une fonction g traitant des listes.


entrer la description de l'image ici


Ainsi, la propriété universelle des plis stipule que:

  g = foldr kv 

g doit être équivalent aux deux équations, pour certains k et v :

  g [] = v g (x:xs) = kx (g xs) 

De nos conceptions antérieures de foldl, nous soaps v == id . Pour la deuxième équation, il faut calculer la définition de k :

  g (x:xs) = kx (g xs) <=> g (x:xs) v = kx (g xs) v -- accumulator of functions <=> g xs (fvx) = kx (g xs) v -- definition of foldl <= g' (fvx) = kxg' v -- generalize (g xs) to g' <=> k = \xg' -> (\a -> g' (fvx)) -- expand k. recursion captured in g' 

La substitution de nos définitions calculées de k et v donne une définition de foldl comme:

 foldl :: (a -> b -> a) -> a -> [b] -> a foldl fv xs = foldr (\xg -> (\a -> g (fvx))) id xs v 

Le g récursif est remplacé par le combinateur foldr, et l’accumulateur devient une fonction construite par une chaîne de compositions de f à chaque élément de la liste, dans l’ordre inverse (nous plions donc à gauche plutôt qu’à droite).

Ceci est certainement un peu avancé, alors pour comprendre profondément cette transformation, la propriété universelle des plis , qui rend la transformation possible, je recommande le tutoriel de Hutton, lié ci-dessous.


Les références

  • Haskell Wiki: foldr et foldr
  • Un tutoriel sur l’universalité et l’expressivité du pli , Graham Hutton, J. Programmation fonctionnelle 9 (4): 355–372, juillet 1999.
  • Malcolm, G. Types de données algébriques et transformation de programme. , Thèse de doctorat, Université de Groningen.

Considérons le type de foldr :

 foldr :: (b -> a -> a) -> a -> [b] -> a 

Alors que le type de step est quelque chose comme b -> (a -> a) -> a -> a . Etant donné que step est passé à foldr , nous pouvons conclure que dans ce cas, le pli a un type comme (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a) .

Ne soyez pas confus par les différentes significations de a dans différentes signatures; c’est juste une variable de type. De plus, gardez à l’esprit que la flèche de fonction est associative droite, donc a -> b -> c est la même chose a -> (b -> c) .

Donc, oui, la valeur de l’accumulateur pour le foldr est une fonction du type a -> a , et la valeur initiale est id . Cela a du sens, car id est une fonction qui ne fait rien – c’est la même raison que vous commenceriez avec zéro comme valeur initiale lorsque vous ajoutez toutes les valeurs d’une liste.

En ce qui concerne la prise de trois arguments, essayez de la réécrire comme suit:

 step :: b -> (a -> a) -> (a -> a) step xg = \a -> g (fax) 

Est-ce que cela rend plus facile de voir ce qui se passe? Il prend un paramètre supplémentaire car il renvoie une fonction et les deux manières de l’écrire sont équivalentes. Notez également le paramètre supplémentaire après le foldr : (foldr step id xs) z . La partie entre parenthèses est le pli lui-même, qui renvoie une fonction, qui est ensuite appliquée à z .

Voici ma preuve que foldl peut être exprimé en termes de foldr , que je trouve assez simple en dehors du nom de spaghetti que la fonction step introduit.

La proposition est que foldl fz xs est équivalent à

 myfoldl fz xs = foldr step_f id xs z where step_f xga = g (fax) 

La première chose importante à noter ici est que le côté droit de la première ligne est en fait évalué comme

 (foldr step_f id xs) z 

car foldr ne prend que trois parameters. Cela indique déjà que le foldr calculera non pas une valeur mais une fonction curry, qui est ensuite appliquée à z . Il y a deux cas à étudier pour savoir si myfoldl est foldl :

  1. Cas de base: liste vide

      myfoldl fz [] = foldr step_f id [] z (by definition of myfoldl) = id z (by definition of foldr) = z foldl fz [] = z (by definition of foldl) 
  2. Liste non vide

      myfoldl fz (x:xs) = foldr step_f id (x:xs) z (by definition of myfoldl) = step_f x (foldr step_f id xs) z (-> apply step_f) = (foldr step_f id xs) (fzx) (-> remove parentheses) = foldr step_f id xs (fzx) = myfoldl f (fzx) xs (definition of myfoldl) foldl fz (x:xs) = foldl f (fzx) xs 

Puisque dans 2. la première et la dernière ligne ont la même forme dans les deux cas, elle peut être utilisée pour replier la liste jusqu’à xs == [] , auquel cas 1. garantit le même résultat. Donc, par induction, myfoldl == foldl .

(parcourez rapidement mes réponses [1] , [2] , [3] , [4] pour vous assurer de comprendre la syntaxe de Haskell, les fonctions d’ordre supérieur, le curry, la composition des fonctions, l’opérateur $, les opérateurs infixes / préfixes, les sections et les lambda )

Propriété universelle de fold

Un pli n’est qu’une codification de certains types de récursivité. Et la propriété d’universalité indique simplement que, si votre récursivité est conforme à une certaine forme, elle peut être transformée en pli selon certaines règles formelles. Et inversement, chaque pli peut être transformé en une récursivité de ce type. Encore une fois, certaines récursions peuvent être traduites en plis qui donnent exactement la même réponse, et certaines récurrences ne peuvent pas l’être, et il existe une procédure exacte pour le faire.

Fondamentalement, si votre fonction récursive fonctionne sur des listes et ressemble à la gauche , vous pouvez la transformer en une droite , en remplaçant f et v par ce qui existe réellement.

 g [] = v ⇒ g (x:xs) = fx (g xs) ⇒ g = foldr fv 

Par exemple:

 sum [] = 0 {- recursion becomes fold -} sum (x:xs) = x + sum xs ⇒ sum = foldr 0 (+) 

Ici v = 0 et sum (x:xs) = x + sum xs est équivalent à sum (x:xs) = (+) x (sum xs) , donc f = (+) . 2 autres exemples

 product [] = 1 product (x:xs) = x * product xs ⇒ product = foldr 1 (*) length [] = 0 length (x:xs) = 1 + length xs ⇒ length = foldr (\_ a -> 1 + a) 0 

Exercice:

  1. Implémenter la map , filter , reverse , concat et concatMap récursivement, tout comme les fonctions ci-dessus sur le côté gauche .

  2. Convertissez ces 5 fonctions en foldr selon une formule cidessus , c’est-à-dire en remplaçant f et v dans la formule de pliage à droite .

Foldl via foldr

Comment écrire une fonction récursive qui additionne les chiffres de gauche à droite?

 sum [] = 0 -- given `sum [1,2,3]` expands into `(1 + (2 + 3))` sum (x:xs) = x + sum xs 

La première fonction récursive qui parvient à trouver une extension complète avant même de commencer à s’append, ce n’est pas ce dont nous avons besoin. Une approche consiste à créer une fonction récursive avec accumulateur , qui additionne immédiatement les nombres à chaque étape (pour en savoir plus sur les stratégies de récursivité, consultez la récursion de la queue ):

 suml :: [a] -> a suml xs = suml' xs 0 where suml' [] n = n -- auxiliary function suml' (x:xs) n = suml' xs (n+x) 

D’accord, arrêtez! Exécutez ce code dans GHCi et assurez-vous de bien comprendre son fonctionnement, puis procédez avec précaution et reflection. suml ne peut pas être redéfini avec un pli, mais suml' peut être.

 suml' [] = v -- equivalent: vn = n suml' (x:xs) n = fx (suml' xs) n 

suml' [] n = n de la définition de la fonction, non? Et v = suml' [] de la formule de propriété universelle. Ensemble, cela donne vn = n , une fonction qui retourne immédiatement ce qu’elle reçoit: v = id . Calculons f :

 suml' (x:xs) n = fx (suml' xs) n -- expand suml' definition suml' xs (n+x) = fx (suml' xs) n -- replace `suml' xs` with `g` g (n+x) = fxgn 

Ainsi, suml' = foldr (\xgn -> g (n+x)) id et, donc, suml = foldr (\xgn -> g (n+x)) id xs 0 .

 foldr (\xgn -> g (n + x)) id [1..10] 0 -- return 55 

Maintenant, il suffit de généraliser, remplacer + par une fonction variable:

 foldl fa xs = foldr (\xgn -> g (n `f` x)) id xs a foldl (-) 10 [1..5] -- returns -5 

Conclusion

Maintenant, lisez le tutoriel de Graham Hutton sur l’universalité et l’expressivité des plis . Obtenez du stylo et du papier, essayez de comprendre tout ce qu’il écrit jusqu’à ce que vous obteniez la plupart des plis par vous-même. Ne pas transpirer si vous ne comprenez pas quelque chose, vous pouvez toujours revenir plus tard, mais ne remettez pas trop en cause non plus.

Il n’y a pas de route royale vers les mathématiques, ni même à travers Haskell. Laisser

 hz = (foldr step id xs) z where step xg = \a -> g (fax) 

Qu’est-ce que c’est que hz ? Supposons que xs = [x0, x1, x2] .
Appliquer la définition de foldr:

 hz = (step x0 (step x1 (step x2 id))) z 

Appliquer la définition de l’étape:

 = (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z 

Remplacer dans les fonctions lambda:

 = (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (fz x0) = (\a2 -> id (f a2 x2)) (f (fz x0) x1) = id (f (f (fz x0) x1) x2) 

Appliquer la définition de l’ID:

 = f (f (fz x0) x1) x2 

Appliquer la définition de foldl:

 = foldl fz [x0, x1, x2] 

Est-ce une route royale ou quoi?

Cela pourrait aider, j’ai essayé de m’étendre différemment.

 myFoldl (+) 0 [1,2,3] = foldr step id [1,2,3] 0 = foldr step (\a -> id (a+3)) [1,2] 0 = foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = foldr step (\b -> id ((b+2)+3)) [1] 0 = foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = foldr step (\c -> id (((c+1)+2)+3)) [] 0 = (\c -> id (((c+1)+2)+3)) 0 = ...