Implémenter zip en utilisant foldr
-
04-07-2019 - |
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?
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)