haskell functional-programming fold combinators

haskell - Implementar zip usando foldr



functional-programming combinators (7)

Actualmente estoy en el capítulo 4 de Real World Haskell, y estoy tratando de entender qué es 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 progresando. ¿Es posible?

Encontré una manera 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 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))

El foldr da foldr resultado una función que, cuando se aplica a una lista, devuelve el zip de la lista plegada con la lista asignada a la función. El Haskell oculta el lambda interno debido a la evaluación perezosa.

Para dividirlo más:

Tome la entrada zip on: ''(1 2 3) El func foldr se llama 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 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 función 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é esta 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 recordarás, f zips su argumento con 3 .

Y esto continúa, etc ...

La respuesta ya se ha dado aquí, pero no una derivación (ilustrativa). Entonces, 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 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 no está forzando en su segundo argumento , primero funciona en x1 e 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 información de izquierda a derecha a lo largo de la lista, llamando a r1 con el resto de la lista de entrada ys1 , foldr fz [x2,x3,...,xn] ys1 = f x2 ys1 r2 ys1 , como el siguiente paso. Y eso es eso.

Cuando ys es más corto que xs (o la misma longitud), el caso [] de ffres y el procesamiento se detiene. Pero si ys es más largo que xs entonces el caso de f ''s [] no se disparará y llegaremos a la aplicación f xn z (yn:ysn) ,

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

Como hemos llegado al final de xs , el procesamiento 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 una continuación de éxito , que llama cuando el procesamiento debe continuar, después de haber emitido el par (x,y) .

Así que r es "lo que se hace con más ys cuando hay más x s" , y z = const [] , el nil -case en foldr , es "lo que se hace con ys cuando ya no hay 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 a la siguiente (el paso "acumular" es, aquí, quitarle un elemento principal).

Naturalmente, esto corresponde al pliegue izquierdo, donde un paso de acumulación es "aplicar la función", con z = id devuelve 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 puede decidir si continuar o no, ahora es posible tener un doblez izquierdo que puede detenerse temprano:

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 pliegue, foldlWhen t ... , con

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

etc.

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 ambos son "buenos productores", en el lenguaje de la lista de fusión. Lo que realmente necesita es una solución que se pliega en ambas listas. Afortunadamente, hay un artículo sobre exactamente eso, llamado "pliegues Coroutining con hiperfunciones" .

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 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 esta es la identidad:

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

También necesita algo que ignora 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 cadenas de todas las funciones push ed juntas, de extremo a extremo, hasta que toque una base o bucles infinitamente.

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 que doblar ambas listas importa es por algo que GHC llama fusión de listas , de lo que 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 la producción inútil y el consumo inmediato de elementos de lista, y puede exponer más optimizaciones.

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

zip xs ys = foldr step done xs ys

Aquí tenemos que derivar step y done , sean lo que sean. foldr el tipo de foldr , instanciado en listas:

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

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

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

Porque -> tiene una asociación correcta , esto es equivalente a:

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

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

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] expande a:

1 + (2 + (3 + 0))

Por lo tanto, si xs = [1,2,3] y ys = [4,5,6,7] , nuestra invocación de 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)) debe crear una función recursiva que pasará por [4,5,6,7] y comprimir 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, como 0 en foldr (+) 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? Usted devuelve la lista vacía [] . Pero recuerda la firma del tipo done :

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

Por lo tanto, no podemos devolver solo [] , debemos devolver una función que ignore lo que reciba. Por lo tanto, use const :

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

Ahora comencemos a pensar qué step debería ser. 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 de xs y ys originales). Por lo tanto, 3 `step` done debe evaluar en:

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

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

Ahora que asumimos cómo debería evaluarse exactamente el step , continuemos 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 damos cuenta de que y se está quedando sin elementos al principio al 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 te sientes inspirado por la elegancia de los pliegues, lee Writing foldl con foldr y luego el tutorial A de Graham Hutton sobre la universalidad y expresividad de fold .

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)

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

Cómo idearlo: comencé con la idea general (de ejemplos similares vistos anteriormente), escribí

zip2 xs ys = foldr step done xs ys

luego llenó cada una de las siguientes líneas con lo que tenía que ser para hacer que los tipos y valores salieran bien. Era más fácil considerar los casos más simples antes que los más difíciles.

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

zip2 = foldr step done

como Mattiast mostró.