Implémenter zip en utilisant foldr

StackOverflow https://stackoverflow.com/questions/235148

Question

Je suis actuellement au chapitre 4 de Real World Haskell et j'essaie de comprendre ce que je pense implémenter foldl en termes de foldr .

(Voici leur code:) 

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

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

Je pensais que j'essaierais de mettre en œuvre zip en utilisant la même technique, mais je ne semble pas progresser. Est-ce même possible?

Était-ce utile?

La solution 

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

Comment cela fonctionne: (foldr step done xs) retourne une fonction qui consomme ys; donc nous descendons la liste des xs en construisant une composition imbriquée de fonctions qui seront appliquées à la partie correspondante de ys.

Comment le trouver: j’ai commencé par l’idée générale (à partir de exemples précédents), a écrit 

zip2 xs ys = foldr step done xs ys

a ensuite rempli chacune des lignes suivantes à tour de rôle être de faire les types et les valeurs sortent bien. Il était plus facile de considérons d’abord les cas les plus simples avant les plus difficiles.

La première ligne pourrait être écrite plus simplement comme 

zip2 = foldr step done

comme mattiast l'a montré.

Autres conseils

La réponse avait déjà été donnée ici, mais pas une dérivation (illustrative). Donc, même après toutes ces années, cela vaut peut-être la peine d'être ajouté.

C'est en fait assez simple. Tout d'abord, 

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn])
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))

donc par eta-expansion, 

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys

Comme cela apparaît clairement ici, si f ne forcent pas dans son deuxième argument , il se met au travail en premier sur x1 et ys , f x1 r1 ys où r1 = (f x2 (f x3 (... (f x z) ...))) = foldr fz [x2, x3, ..., xn] .

Donc, en utilisant 

f x1 r1 [] = []
f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1

nous organisons le passage des informations de gauche à droite le long de la liste, par appelant r1 avec le reste de la liste d'entrée ys1 , foldr fz [x2, x3, ..., xn] < code> ys1 = f x2 r2 ys1 , comme étape suivante. Et c'est ça.

Lorsque ys est plus court que xs (ou la même longueur), la casse [] pour f les incendies et le traitement s'arrête. Mais si ys est plus long que xs , la casse de f de [] ne fonctionnera pas et nous accéder à la dernière f xn z (yn: ysn) , 

f xn z (yn:ysn) = (xn,yn) : z ysn

Depuis la fin de xs , le traitement de zip doit cesser: 

z _ = []

Et cela signifie que la définition z = const [] doit être utilisée: 

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

Du point de vue de f , r joue le rôle d'une continuation de la réussite , que f appelle lorsque le traitement doit continuer après avoir émis le couple (x, y) .

Donc r est "ce qui est fait avec plus de ys quand il y a plus de x s" , " et z = const [] , le nil -case dans foldr , est "ce qui est terminé avec ys lorsqu'il n'y a plus de x s " . Ou bien f peut s'arrêter de lui-même en renvoyant [] lorsque ys est épuisé.

Notez comment ys est utilisé comme une sorte de valeur d'accumulation, transmise de gauche à droite le long de la liste xs , à partir de l'invocation de f à l'étape suivante (l'étape "accumulatrice" étant, ici, le dépouillement d'un élément de tête).

Naturellement , cela correspond au repli gauche, où une étape d'accumulation consiste à "appliquer la fonction", avec z = id renvoyant la valeur finale accumulée lorsque "il n'y a plus de x s": 

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

De même, pour les listes finies, 

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

Et puisque la fonction de combinaison doit décider de continuer ou non, il est maintenant possible d'avoir un pli gauche qui peut s'arrêter plus tôt: 

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

ou un pli gauche gauche, foldlWhen t ... , avec 

    cons x r a = if t x then r (f a x) else r a

etc.

J'ai trouvé un moyen d'utiliser une méthode assez similaire à la vôtre: 

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

Pour les Haskellers non natifs ici, j'ai écrit une version Scheme de cet algorithme afin de clarifier ce qui se passe réellement: 

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

Le foldr a pour résultat une fonction qui, lorsqu'elle est appliquée à une liste, renverra le zip de la liste repliée avec la liste donnée à la fonction. Haskell masque le lambda interne à cause d'une évaluation paresseuse.

Pour décomposer davantage:

Prenez le zip à l'entrée: '(1 2 3) Le foldr func est appelé avec 

el->3, func->(lambda (a) empty)

Ceci se développe en: 

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

Si nous devions renvoyer ceci maintenant, nous aurions une fonction qui prend la liste d'un élément et retourne la paire (3 élément): 

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

Continuant, foldr appelle maintenant func avec 

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

C’est une fonction qui prend une liste avec deux éléments, maintenant, et les zippe avec (liste 2 3) : 

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

Qu'est-ce qui se passe? 

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

a , dans ce cas, est (liste 9 1) 

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

Et, comme vous vous en souvenez, f compresse son argument avec 3 .

Et cela continue etc ...

Le problème avec toutes ces solutions pour zip est qu’elles ne se chevauchent que sur une liste, ce qui peut poser problème si les deux sont de "bons producteurs", dans le jargon de fusion de liste. Ce dont vous avez réellement besoin, c’est d’une solution qui regroupe les deux listes. Heureusement, il existe un document à ce sujet, intitulé "Corriger les plis avec des hyperfonctions" .

Vous avez besoin d'un type auxiliaire, d'une hyperfonction, qui est fondamentalement une fonction qui prend un autre hyperfonction comme argument. 

newtype H a b = H { invoke :: H b a -> b }

Les hyperfonctions utilisées ici agissent essentiellement comme des "piles". des fonctions ordinaires. 

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

Vous avez également besoin d'un moyen de mettre bout à bout deux hyperfonctions. 

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

Ceci est lié à push par la loi: 

(push f x) .#. (push g y) = push (f . g) (x .#. y)

Il s’avère qu’il s’agit d’un opérateur associatif et il s’agit de l’identité: 

self :: H a a
self = H $ \k -> invoke k self

Vous avez également besoin de quelque chose qui ignore tout le reste de la "pile". et renvoie une valeur spécifique: 

base :: b -> H a b
base b = H $ const b

Et enfin, vous avez besoin d’un moyen de tirer une valeur d’un hyperfonctionnement: 

run :: H a a -> a
run q = invoke q self

exécuter chaîne toutes les fonctions push ed ensemble, bout à bout, jusqu'à atteindre une base ou une boucle infinie.

Vous pouvez donc maintenant plier les deux listes en hyperfonctions, en utilisant des fonctions qui transmettent des informations de l'une à l'autre et assembler la valeur finale. 

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

La raison pour laquelle le repliement sur les deux listes est important est due à quelque chose que GHC a appelé liste de fusion , dont il est question dans le module GHC.Base , mais devrait probablement être beaucoup plus connu. Être un bon producteur de liste et utiliser build avec foldr peut empêcher de nombreuses productions inutiles et la consommation immédiate d'éléments de liste, et peut révéler d'autres optimisations.

J’ai essayé de comprendre cette solution élégante moi-même, j’ai donc essayé d’en déduire les types et les évaluations moi-même. Nous devons donc écrire une fonction: 

zip xs ys = foldr step done xs ys

Ici, nous devons dériver step et done , quels qu'ils soient. Rappelez foldr Type , instancié en listes: 

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

Cependant, notre invocation foldr doit être instanciée comme ci-dessous, car nous devons accepter non pas un, mais deux arguments de liste: 

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

Comme - > est right-associative , cela équivaut à: 

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

Notre ([b] - > [(a, b)]) correspond à la variable de type state du type foldr d'origine signature, nous devons donc remplacer chaque occurrence de state par celle-ci: 

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

Cela signifie que les arguments que nous passons à foldr doivent avoir les types suivants: 

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

Rappelez-vous que foldr (+) 0 [1,2,3] se développe en: 

1 + (2 + (3 + 0))

Donc si xs = [1,2,3] et ys = [4,5,6,7] , notre foldr l'invocation serait étendue à: 

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

Cela signifie que notre construction 1 `step` (2` step` (3 `step` done)) doit créer une fonction récursive qui passerait par [4,5,6 , 7] et compressez les éléments. (Gardez à l'esprit que si l'une des listes d'origine est plus longue, les valeurs excédentaires sont supprimées). IOW, notre construction doit avoir le type [b] - > [(a, b)] .

3 `step` done est notre cas de base, où done est une valeur initiale, comme 0 dans foldr (+ ) 0 [1..3] . Nous ne voulons rien compresser après 3, car 3 est la valeur finale de xs , nous devons donc mettre fin à la récursivité. Comment résiliez-vous la liste de récurrence sur le scénario de base? Vous retournez une liste vide [] . Mais rappelons done la signature de type: 

done :: [b] -> [(a,b)]

Par conséquent, nous ne pouvons pas simplement renvoyer [] , nous devons renvoyer une fonction qui ignore tout ce qu'elle reçoit. Par conséquent, utilisez const : 

done = const [] -- this is equivalent to done = \_ -> []

Maintenant, commençons à déterminer ce que doit être step . Il combine une valeur de type a avec une fonction de type [b] - > [(a, b)] et renvoie une fonction de type [b] - > [(a, b)] .

Dans 3 `step` done , nous savons que la valeur du résultat qui ira plus tard dans notre liste compressée doit être (3,6) (sachant depuis l'original < code> xs et ys ). Par conséquent, 3 `step` done doit être évalué dans: 

\(y:ys) -> (3,y) : done ys

N'oubliez pas que nous devons renvoyer une fonction, à l'intérieur de laquelle nous zippons les éléments. Le code ci-dessus est ce qui a du sens et les vérifications de type.

Maintenant que nous supposons comment exactement step doit évaluer, poursuivons l'évaluation. Voici à quoi ressemblent toutes les étapes de réduction de notre foldr : 

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

L’évaluation donne lieu à cette implémentation de l’étape (notez que nous tenons compte du fait que ys manque d’éléments en renvoyant une liste vide): 

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

Ainsi, la fonction complète zip est implémentée comme suit: 

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

PS: Si vous êtes inspiré par l’élégance des plis, lisez Écrire un foldl avec foldr et ensuite de Graham Hutton. Un tutoriel sur l'universalité et l'expressivité du pli .

Une approche simple: 

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top