Implementar zip usando foldr

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

Pregunta

Actualmente estoy en el capítulo 4 de Real World Haskell, y estoy tratando de entender implementando foldl en términos de foldr .

(Aquí está 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 intentaría implementar zip usando la misma técnica, pero parece que no estoy haciendo ningún progreso. ¿Es incluso posible?

¿Fue útil?

Solución 

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: (foldr step done xs) devuelve una función que consume ys; así que vamos a la lista xs construyendo una composición anidada de funciones que se aplicarán a la parte correspondiente de ys.

Cómo encontrarlo: comencé con la idea general (de similar ejemplos vistos antes), escribieron 

zip2 xs ys = foldr step done xs ys

luego completó cada una de las siguientes líneas a su vez con lo que tenía que Ser para que los tipos y valores salgan bien. Fue más fácil considere los casos más simples primero antes que los más difíciles.

La primera línea podría escribirse más simplemente como 

zip2 = foldr step done

como mostró mattiast.

Otros consejos

La respuesta ya se había dado aquí, pero no una derivación (ilustrativa). Así que incluso después de todos estos años, quizás valga la pena agregarlo.

En realidad es bastante simple. Primero, 

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 expansión eta, 

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 no tiene forzamiento en su segundo argumento , se pone a trabajar primero en x1 y ys , f x1 r1 ys donde r1 = (f x2 (f x3 (... (f xn z) ...))) = foldr fz [x2, x3, ..., xn] .

Entonces, usando 

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

organizamos el paso de la información de izquierda a derecha a lo largo de la lista, llamando r1 con el resto de la lista de entrada ys1 , foldr fz [x2, x3, ..., xn] < código> ys1 = f x2 r2 ys1 , como el siguiente paso. Y eso es todo.

Cuando ys es más corto que xs (o la misma longitud), el caso [] para f incendios y el procesamiento se detiene. Pero si ys es más largo que xs , el caso [] de f no se activará y nosotros llegar a la aplicación final de f xn z (yn: ysn) , 

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

Desde que llegamos al final de xs , el proceso de zip debe detenerse: 

z _ = []

Y esto significa que se debe usar la definición z = const [] : 

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 f , r desempeña el papel de continuación de éxito , que f llama cuando el proceso debe continuar, después de haber emitido el par (x, y) .

Entonces r es " lo que se hace con más ys cuando hay más x s " , y z = const [] , nil -case en foldr , es " lo que es hecho con ys cuando no hay más x s " . O f puede detenerse por sí mismo, devolviendo [] cuando ys está agotado.

Observe cómo ys se usa como un tipo de valor acumulado, que se pasa de izquierda a derecha a lo largo de la lista xs , de una invocación de f al siguiente (" acumulando " el paso es, aquí, quitarle un elemento de cabeza).

Naturalmente esto corresponde al pliegue izquierdo, donde un paso de acumulación es "aplicar la función " ;, con z = id devolviendo 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

Del mismo modo, para listas finitas, 

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

Y dado que la función de combinación decide si continuar o no, ahora es posible tener un pliegue a la izquierda que puede detenerse antes: 

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 un salto hacia la izquierda, foldlWhen t ... , with 

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

etc.

Encontré una forma de usar un método bastante similar al tuyo: 

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 aquí, he escrito una versión Scheme de este algoritmo para aclarar lo que realmente está sucediendo: 

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

El foldr da como resultado una función que, cuando se aplica a una lista, devolverá el zip de la lista doblada con la lista dada a la función. El Haskell oculta el lambda interno debido a la perezosa evaluación.

Para desglosarlo aún más:

Tomar zip en la entrada: '(1 2 3) Se llama a la función foldr con 

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

Esto se 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 elementos): 

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

Continuando, foldr ahora llama a 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))))

Este es un func que toma una lista con dos elementos, ahora, y los comprime 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 (lista 9 1) 

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

Y, como recordará, f comprime su argumento con 3 .

Y esto continúa, etc ...

El problema con todas estas soluciones para zip es que solo se pliegan sobre una lista u otra, lo que puede ser un problema si ambos son '' buenos productores '', en el lenguaje de lista de fusión. Lo que realmente necesita es una solución que se pliegue sobre ambas listas. Afortunadamente, hay un documento sobre eso exactamente, llamado " Pliegues de la redacción con hiperconfunciones " .

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

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 principio a fin. 

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

Esto está relacionado con push por ley: 

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

Esto resulta ser un operador asociativo, y esta es la identidad: 

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

También necesitas algo que no tenga en cuenta todo lo demás en la " pila " y devuelve un valor específico: 

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

Y finalmente, necesita una forma de obtener un valor de una hiperfunción: 

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

run combina todas las funciones ed push juntas, de extremo a extremo, hasta que golpea una base o realiza un bucle infinito.

Entonces 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 la cual el plegado sobre ambas listas es importante es por algo que GHC llama list fusion , del cual se habla en el módulo GHC.Base , pero probablemente debería ser mucho más conocido. Ser un buen productor de listas y usar build con foldr puede evitar mucha producción inútil y consumo inmediato de elementos de lista, y puede exponer más optimizaciones.

Traté de comprender esta elegante solución, así que intenté derivar los tipos y la evaluación por mí mismo. Entonces, necesitamos escribir una función: 

zip xs ys = foldr step done xs ys

Aquí necesitamos derivar paso y hecho , cualesquiera que sean. Recuerde foldr tipo, instanciado a listas: 

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

Sin embargo, nuestra invocación foldr debe ser instanciada a algo como a continuación, porque debemos aceptar no uno, sino dos argumentos de lista: 

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

Debido a que - > es asociativo a la derecha , esto es equivalente a: 

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

Nuestra ([b] - > [(a, b)]) corresponde a la variable de tipo state en el tipo original foldr firma, por lo tanto, debemos reemplazar cada aparición de estado con: 

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]

Recuerde 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] , nuestro foldr la invocación se expandiría a: 

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

Esto significa que nuestra construcción 1 `step` (2` step` (3 `step` done)) debe crear una función recursiva que pasaría por [4,5,6 , 7] y comprima los elementos. (Tenga en cuenta que si una de las listas originales es más larga, los valores en exceso se desechan). IOW, nuestra construcción debe tener el tipo [b] - > [(a, b)] .

3 `step` done es nuestro caso base, donde done es un valor inicial, como 0 en foldr (+ ) 0 [1..3] . No queremos comprimir nada después de 3, porque 3 es el valor final de xs , por lo que debemos terminar la recursión. ¿Cómo termina la recursión sobre la lista en el caso base? Devuelve la lista vacía [] . Pero recuerde la firma de tipo done : 

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

Por lo tanto, no podemos devolver solo [] , debemos devolver una función que ignoraría lo que recibe. Por lo tanto, use const : 

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

Ahora comencemos a descubrir qué debe ser el paso . Combina un valor de tipo a con una función de tipo [b] - > [(a, b)] y devuelve una función de tipo [b] - > [(a, b)] .

En 3 `step` done , sabemos que el valor del resultado que luego iría a nuestra lista comprimida debe ser (3,6) (sabiendo del original < code> xs y ys ). Por lo tanto, 3 `step` done debe evaluarse en: 

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

Recuerde, debemos devolver una función, dentro de la cual de alguna manera comprimimos los elementos, el código anterior es lo que tiene sentido y escribe.

Ahora que asumimos cómo se debe evaluar exactamente step , continuemos con la evaluación. Así es como se ven todos los pasos de reducción en nuestra evaluación de 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)

La evaluación da lugar a esta implementación del paso (tenga en cuenta que tenemos en cuenta que ys se queda sin elementos antes de devolver 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 Escribir pliegue usando foldr y luego Graham Hutton's Un tutorial sobre la universalidad y la expresividad del doblez .

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)
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top