Actualmente estoy en el capítulo 4 de Real World Haskell, y estoy tratando de ajustar mi cabeza alrededor de implementing foldl in terms of foldr.Implementar zip usando foldr
(Aquí es su código :)
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)
pensé que iba a tratar de poner en práctica zip utilizando la misma técnica, pero no parece que estar haciendo ningún progreso. ¿Es posible?
zip2 xs ys = foldr step done xs ys
where done ys = []
step x zipsfn [] = []
step x zipsfn (y:ys) = (x, y) : (zipsfn ys)
¿Cómo funciona esto: (paso foldr XS hecho) devuelve una función que consume ys; así que bajamos por la lista xs construyendo una composición anidada de las funciones que se aplicarán a la parte correspondiente de ys.
Cómo para llegar a ella: Empecé con la idea general (de ejemplos similares visto antes), escribí
zip2 xs ys = foldr step done xs ys
luego se llena en cada una de las siguientes líneas a su vez, con lo que tenía que hacer que los tipos y valores salgan bien. Fue más fácil para considerar los casos más simples primero antes que los más difíciles.
La primera línea se podría escribir más simplemente como
zip2 = foldr step done
como mattiast mostraron.
he encontrado una manera usando el método bastante similar a la suya:
myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
where step a f (b:bs) = (a,b):(f bs)
step a f [] = []
Para los Haskellers no nativos de aquí, he escrito una versión Esquema de este algoritmo para hacerlo más claro de lo que está sucediendo realmente:
> (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))
Los foldr resulta en una función que, cuando se aplica a una lista , devolverá el zip de la lista doblado con la lista dada a la función. El Haskell oculta el interior lambda debido a la evaluación perezosa.
descomponerlo además: zip
toma en entrada: '(1 2 3) La func foldr se llama con
el->3, func->(lambda (a) empty)
Esto expande a:
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))
Si tuviéramos que devolver esto ahora, tendríamos una función que toma una lista de un elemento y devuelve el par (3 elemento):
> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))
Continua, foldr ahora llama func con
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))))
Esta es una func que toma una lista con dos elementos, ahora, y ellos cremalleras con (list 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á pasando?
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))
a, en este caso, es (list 9 1)
(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))
Y, como se recordará, f cremalleras su discusión con 3.
Y esto continúa etc ...
La respuesta ya había sido dada aquí, pero no una derivación (ilustrativo). Entonces, incluso después de todos estos años, quizás valga la pena agregarlo.
En realidad es bastante simple. En primer lugar,
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) ...)))
por lo tanto, por ETA-expansión,
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
Como es evidente aquí, si f es no forzar en su segundo argumento, se pone a trabajar primera en x1 y ys, f x1r1ys donde r1 =(f x2 (f x3 (... (f xn z) ...)))= foldr f z [x2,x3,...,xn].
Por lo tanto, el uso de
f x1 r1 [] = [] f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1
disponemos para el paso de la información de izquierda a derecha lo largo de la lista, por llamandor1 con el resto de la lista de entrada ys1, foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1, como el próximo paso. Y eso es eso.
Cuando ys es más corta que xs (o la misma longitud), el caso [] para f incendios y el proceso se detiene. Pero si es más largo que ysxs continuación f 's [] caso no va a disparar y vamos a llegar a la final de la aplicación f xnz(yn:ysn),
f xn z (yn:ysn) = (xn,yn) : z ysn
Desde que hemos llegado al final de xs, la zip procesamiento debe parar:
z _ = []
Y esto significa que eldefiniciónse debe utilizar:
zip xs ys = foldr f (const []) xs ys
where
f x r [] = []
f x r (y:ys) = (x,y) : r ys
Desde el punto de vista de fr, juega el papel de una continuación del éxito , que f llamadas cuando el proceso ha de continuar, después de haber emitido el par (x,y).
Así r es "lo que se hace con más ys cuando hay más x s" y z = const [], la -case nil en foldr, es "Lo que se hace con ys cuando no hay más x s ". O f puede detenerse por sí mismo, devolviendo [] cuando se agota ys.
Observe cómo se utiliza ys como una especie de valor de acumulación, que se pasa de izquierda a derecha a lo largo de la lista xs, de una invocación de f a la siguiente ("acumulación" paso de ser, aquí, de despojarla elemento principal de ella).
Naturally esto corresponde al pliegue izquierda, donde un paso de acumulación es "la aplicación de la función", con z = id devolver el valor acumulado final cuando "no hay más x s":
foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a
mismo modo, para listas finitas,
foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a
Y puesto que la función de la combinación puede decidir si continuar o no, ahora es posible a veces han dejado que puede detener principios:
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
o una omisión de la izquierda pliegue, foldlWhen t ..., con
cons x r a = if t x then r (f a x) else r a
etc.
traté de entender este elegante solución a mí mismo, por lo que trataron de obtener los tipos y evaluación de mí mismo. Por lo tanto, tenemos que escribir una función:
zip xs ys = foldr step done xs ys
Aquí tenemos que derivar step y done, cualesquiera que sean. Tipo recuerdo foldr 's, una instancia de listas:
foldr :: (a -> state -> state) -> state -> [a] -> state
Sin embargo nuestra foldr invocación debe ser instanciada a algo parecido a continuación, porque hay que aceptar no uno, sino dos listas de argumentos:
foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]
Debido -> es right-associative, esto es equivalente a:
foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])
Nuestra ([b] -> [(a,b)]) corr esponds a state variable de tipo en la firma foldr tipo original, por lo tanto, hay que reemplazar todas las apariciones de state con él:
foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
-> ([b] -> [(a,b)])
-> [a]
-> ([b] -> [(a,b)])
Esto significa que los argumentos que pasamos a foldr deben tener los siguientes tipos:
step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]
Recordemos que foldr (+) 0 [1,2,3] se expande a:
1 + (2 + (3 + 0))
Por lo tanto, si xs = [1,2,3] y ys = [4,5,6,7], nuestra invocación foldr se expandiría a:
1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]
Esto significa que nuestra 1 `step` (2 `step` (3 `step` done)) constructo debe crear una función recursiva que pasaría por [4,5,6,7] y cerrar la cremallera de los elementos. (Tenga en cuenta que si una de las listas originales es más larga, los valores sobrantes se descartan). IOW, nuestra construcción debe tener el tipo [b] -> [(a,b)].
3 `step` done es nuestro caso base, donde done es un valor inicial, al igual que en 0foldr (+) 0 [1..3]. No deseamos comprimir nada después de 3, porque 3 es el valor final de xs, por lo que debemos finalizar la recursión. ¿Cómo terminas la recursión sobre la lista en el caso base? Devuelve la lista vacía []. Pero recordar done tipo de firma:
done :: [b] -> [(a,b)]
Por lo tanto, no se puede devolver sólo [], hay que volver a una función que haga caso omiso de lo que recibe. Por lo tanto utilizar const:
done = const [] -- this is equivalent to done = \_ -> []
Ahora vamos a empezar a averiguar lo que debería haber step. Combina un valor del tipo a con una función del tipo [b] -> [(a,b)] y devuelve una función del tipo [b] -> [(a,b)].
En 3 `step` done, sabemos que el valor del resultado que más tarde pasaría a nuestra lista de cremallera debe ser (3,6) (sabiendo de originales xs y ys). Por lo tanto 3 `step` done debe evaluar en:
\(y:ys) -> (3,y) : done ys
Recuerde, hay que volver a una función, dentro de la cual de alguna manera cerrar la cremallera de los elementos, el código anterior es lo que tiene sentido y typechecks.
Ahora que asumimos cómo debe evaluarse exactamente step, continuemos la evaluación. Así es como todas las medidas de reducción en nuestra evaluación foldr se parecen:
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)
La evaluación da lugar a esta realización de la etapa (nótese que cuenta ys quedarse sin elementos temprana devolviendo una lista vacía):
step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys
Por lo tanto, la función completa zip se implementa de la siguiente manera:
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
PD: Si está inspirado en la elegancia de los pliegues, lea Writing foldl using foldr y luego A tutorial on the universality and expressiveness of fold de Graham Hutton.
El problema con todas estas soluciones para zip es que solo se pliegan en una u otra lista, lo que puede ser un problema si ambas son "buenas productoras", en el lenguaje de lista de fusión. Lo que realmente necesita es una solución que se pliega en ambas listas. Afortunadamente, hay un artículo sobre eso exactamente, llamado "Coroutining Folds with Hyperfunctions".
Necesita un tipo auxiliar, una hiperfunción, que es básicamente una función que toma otra hiperfunción como argumento.
newtype H a b = H { invoke :: H b a -> b }
Las hiperfunciones utilizadas aquí básicamente actúan como una "pila" de funciones normales.
push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q
También necesita una forma de juntar dos hiperfunciones, de extremo a extremo.
(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k
esto está relacionado con push por la ley:
(push f x) .#. (push g y) = push (f . g) (x .#. y)
Esto resulta ser un operador asociativo, y esto es la identidad:
self :: H a a
self = H $ \k -> invoke k self
también necesita algo que hace caso omiso de todo lo demás en la "pila" y devuelve un valor específico:
base :: b -> H a b
base b = H $ const b
Y, por último, se necesita una manera de obtener un valor fuera de una hiperfunción:
run :: H a a -> a
run q = invoke q self
run cuerdas todas las funciones push ed juntos, extremo a extremo, hasta que se realiza un base o bucles infinitamente.
Ahora puede doblar ambas listas en hiperfunciones, usando funciones que pasan información de una a la otra, y ensamblar el valor final.
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 razón por plegado de ambas materias listas es debido a algo que no GHC llama lista fusión, que se habla en the GHC.Base module, pero probablemente debería ser mucho más conocida. Ser un buen productor de listas y usar build con foldr puede evitar la producción inútil y el consumo inmediato de elementos de lista, y puede exponer más optimizaciones.
Un enfoque 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)
¿Cómo funciona esto? ¿No foldr solo toma 3 argumentos? – Claudiu
eres malvado ... ¿no estás diciendo que es diong (foldr step done xs) y luego lo aplicas a ys? – Claudiu
Es el mismo algoritmo que mattiast (quien publicó 4 segundos más rápido). A la derecha, (foldr step done xs) devuelve una función que consume ys; de modo que bajamos por la lista xs construyendo una composición anidada de funciones que se aplicarán a la parte correspondiente de ys. –