foldl haskell recursion fold

foldl - map haskell



Escribir foldl usando foldr (6)

En Real World Haskell , Capítulo 4. Programación funcional

Escribe foldl con foldr:

-- file: ch04/Fold.hs 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)

El código anterior me confundió mucho, y un tipo llamado dps lo reescribió con un nombre significativo para hacerlo un poco más claro:

myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL where stepR lastL accR accInitL = accR (stepL accInitL lastL)

Un hombre Jef G hizo un excelente trabajo al proporcionar un ejemplo y mostrar el mecanismo subyacente paso a paso:

myFoldl (+) 0 [1, 2, 3] = (foldR step id [1, 2, 3]) 0 = (step 1 (step 2 (step 3 id))) 0 = (step 1 (step 2 (/a3 -> id ((+) a3 3)))) 0 = (step 1 (/a2 -> (/a3 -> id ((+) a3 3)) ((+) a2 2))) 0 = (/a1 -> (/a2 -> (/a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0 = (/a1 -> (/a2 -> (/a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0 = (/a1 -> (/a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0 = (/a1 -> (+) ((+) ((+) a1 1) 2) 3) 0 = (+) ((+) ((+) 0 1) 2) 3 = ((0 + 1) + 2) + 3

Pero todavía no puedo entender completamente eso, aquí están mis preguntas:

  1. ¿Para qué sirve la función id? ¿Cuál es el papel de? ¿Por qué deberíamos necesitarlo aquí?
  2. En el ejemplo anterior, la función id es el acumulador en la función lambda?
  3. El prototipo de foldr es foldr :: (a -> b -> b) -> b -> [a] -> b , y el primer parámetro es una función que necesita dos parámetros, pero la función de paso en la implementación de myFoldl usa 3 parámetros ¡Estoy completamente confundido!

Hay alguien que pueda ayudarme? ¡Muchas gracias!

¡Algunas explicaciones están en orden!

¿Para qué sirve la función id? ¿Cuál es el papel de? ¿Por qué deberíamos necesitarlo aquí?

id es la función de identidad , id x = x , y se usa como el equivalente de cero cuando se construye una cadena de funciones con composición de funciones , (.) . Puedes encontrarlo definido en el Preludio .

En el ejemplo anterior, la función id es el acumulador en la función lambda?

El acumulador es una función que se está creando mediante la aplicación de funciones repetidas. No hay una lambda explícita, ya que nombramos el acumulador, step . Puedes escribirlo con un lambda si quieres:

foldl f a bs = foldr (/b g x -> g (f x b)) id bs a

O como escribiría Graham Hutton :

El prototipo de foldr es foldr :: (a -> b -> b) -> b -> [a] -> b

Un programador de Haskell diría que el tipo de foldr es (a -> b -> b) -> b -> [a] -> b .

y el primer parámetro es una función que necesita dos parámetros, pero la función de paso en la implementación de myFoldl usa 3 parámetros, estoy completamente confundido

Esto es confuso y mágico! Jugamos un truco y reemplazamos el acumulador con una función, que a su vez se aplica al valor inicial para producir un resultado.

Graham Hutton explica el truco para convertir foldl en foldr en el artículo anterior. Comenzamos escribiendo una definición recursiva de foldl :

foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x : xs) = foldl f (f v x) xs

Y luego refactorizarlo a través de la transformación de argumento estático en f :

foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v xs = g xs v where g [] v = v g (x:xs) v = g xs (f v x)

Ahora reescribamos g para flotar el v hacia adentro:

foldl f v xs = g xs v where g [] = /v -> v g (x:xs) = /v -> g xs (f v x)

Lo cual es lo mismo que pensar en g como una función de un argumento, que devuelve una función:

foldl f v xs = g xs v where g [] = id g (x:xs) = /v -> g xs (f v x)

Ahora tenemos g , una función que camina recursivamente por una lista, aplica alguna función f . El valor final es la función de identidad, y cada paso da como resultado una función también.

Pero ya tenemos a mano una función recursiva muy similar en las listas, ¡ foldr !

Esto parece un esquema recursivo muy similar a nuestra función g . Ahora el truco: usando toda la magia disponible (aka Bird, Meertens y Malcolm) aplicamos una regla especial, la propiedad universal de fold , que es una equivalencia entre dos definiciones para una función g que procesa listas, expresadas como:

Entonces, la propiedad universal de los pliegues establece que:

g = foldr k v

donde g debe ser equivalente a las dos ecuaciones, para algunos k y v :

g [] = v g (x:xs) = k x (g xs)

De nuestros diseños anteriores de foldl, sabemos v == id . Para la segunda ecuación, sin embargo, necesitamos calcular la definición de k :

g (x:xs) = k x (g xs) <=> g (x:xs) v = k x (g xs) v -- accumulator of functions <=> g xs (f v x) = k x (g xs) v -- definition of foldl <= g'' (f v x) = k x g'' v -- generalize (g xs) to g'' <=> k = /x g'' -> (/a -> g'' (f v x)) -- expand k. recursion captured in g''

Lo cual, sustituyendo nuestras definiciones calculadas de k y v produce una definición de foldl como:

foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v xs = foldr (/x g -> (/a -> g (f v x))) id xs v

El g recursivo se reemplaza por el combinador foldr, y el acumulador se convierte en una función creada mediante una cadena de composiciones de f en cada elemento de la lista, en orden inverso (por lo que doblamos hacia la izquierda en lugar de hacia la derecha).

Esto definitivamente es algo avanzado, así que para entender profundamente esta transformación, la propiedad universal de los pliegues , que hace posible la transformación, recomiendo el tutorial de Hutton, vinculado a continuación.

Referencias

Considere el tipo de foldr :

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

Mientras que el tipo de step es algo así como b -> (a -> a) -> a -> a . Como el paso se pasa a foldr , podemos concluir que en este caso el doblez tiene un tipo como (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a) .

No se confunda con los diferentes significados de a en diferentes firmas; es solo una variable de tipo. Además, tenga en cuenta que la flecha de función es asociativa derecha, por lo que a -> b -> c es lo mismo que a -> (b -> c) .

Entonces, sí, el valor del acumulador para el foldr es una función de tipo a -> a , y el valor inicial es id . Esto tiene algún sentido, porque id es una función que no hace nada, es la misma razón por la que comenzarías con cero como valor inicial al agregar todos los valores en una lista.

En cuanto al step tomar tres argumentos, intente reescribirlo así:

step :: b -> (a -> a) -> (a -> a) step x g = /a -> g (f a x)

¿Eso hace que sea más fácil ver lo que está pasando? Toma un parámetro adicional porque devuelve una función, y las dos formas de escribirlo son equivalentes. Tenga en cuenta también el parámetro extra después del foldr : (foldr step id xs) z . La parte entre paréntesis es el doblez mismo, que devuelve una función, que luego se aplica a z .

Esta es mi prueba de que foldl se puede expresar en términos de foldr , que me parece bastante simple aparte del nombre spaghetti que introduce la función de step .

La proposición es que foldl fz xs es equivalente a

myfoldl f z xs = foldr step_f id xs z where step_f x g a = g (f a x)

Lo primero que hay que notar aquí es que el lado derecho de la primera línea se evalúa como

(foldr step_f id xs) z

ya que foldr solo toma tres parámetros. Esto ya sugiere que el foldr calculará no un valor sino una función curried, que luego se aplica a z . Hay dos casos para investigar para descubrir si myfoldl es foldl :

  1. Caso base: lista vacía

    myfoldl f z [] = foldr step_f id [] z (by definition of myfoldl) = id z (by definition of foldr) = z foldl f z [] = z (by definition of foldl)

  2. Lista no vacía

    myfoldl f z (x:xs) = foldr step_f id (x:xs) z (by definition of myfoldl) = step_f x (foldr step_f id xs) z (-> apply step_f) = (foldr step_f id xs) (f z x) (-> remove parentheses) = foldr step_f id xs (f z x) = myfoldl f (f z x) xs (definition of myfoldl) foldl f z (x:xs) = foldl f (f z x) xs

Como en 2. la primera y la última línea tienen la misma forma en ambos casos, se puede usar para plegar la lista hasta xs == [] , en cuyo caso 1. garantiza el mismo resultado. Entonces por inducción, myfoldl == foldl .

Esto podría ayudar, intenté expandirme de una manera diferente.

myFoldl (+) 0 [1,2,3] = foldr step id [1,2,3] 0 = foldr step (/a -> id (a+3)) [1,2] 0 = foldr step (/b -> (/a -> id (a+3)) (b+2)) [1] 0 = foldr step (/b -> id ((b+2)+3)) [1] 0 = foldr step (/c -> (/b -> id ((b+2)+3)) (c+1)) [] 0 = foldr step (/c -> id (((c+1)+2)+3)) [] 0 = (/c -> id (((c+1)+2)+3)) 0 = ...

No hay un Camino Real a las Matemáticas, ni siquiera a través de Haskell. Dejar

h z = (foldr step id xs) z where step x g = /a -> g (f a x)

¿Qué diablos es hz ? Supongamos que xs = [x0, x1, x2] .
Aplicar la definición de foldr:

h z = (step x0 (step x1 (step x2 id))) z

Aplicar la definición de paso:

= (/a0 -> (/a1 -> (/a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z

Sustituir en las funciones lambda:

= (/a1 -> (/a2 -> id (f a2 x2)) (f a1 x1)) (f z x0) = (/a2 -> id (f a2 x2)) (f (f z x0) x1) = id (f (f (f z x0) x1) x2)

Aplicar definición de id:

= f (f (f z x0) x1) x2

Aplicar la definición de foldl:

= foldl f z [x0, x1, x2]

¿Es un Royal Road o qué?

(hojee rápidamente mis respuestas [1] , [2] , [3] , [4] para asegurarse de que entiende la sintaxis de Haskell, funciones de orden superior, currying, composición de funciones, operador $, operadores de infijo / prefijo, secciones y lambdas )

Propiedad universal de fold

Un fold es solo una codificación de ciertos tipos de recursión. Y la propiedad de universalidad simplemente establece que, si su recursión se ajusta a una determinada forma, puede transformarse en doblez de acuerdo con algunas reglas formales. Y a la inversa, cada pliegue se puede transformar en una recursión de ese tipo. Una vez más, algunas recursiones se pueden traducir en pliegues que dan exactamente la misma respuesta, y algunas recurrencias no, y existe un procedimiento exacto para hacerlo.

Básicamente, si su función recursiva funciona en listas y se ve a la izquierda , puede transformarla para doblar una a la derecha , sustituyendo f y v por lo que realmente está allí.

g [] = v ⇒ g (x:xs) = f x (g xs) ⇒ g = foldr f v

Por ejemplo:

sum [] = 0 {- recursion becomes fold -} sum (x:xs) = x + sum xs ⇒ sum = foldr 0 (+)

Aquí v = 0 y sum (x:xs) = x + sum xs es equivalente a sum (x:xs) = (+) x (sum xs) , por lo tanto, f = (+) . 2 ejemplos más

product [] = 1 product (x:xs) = x * product xs ⇒ product = foldr 1 (*) length [] = 0 length (x:xs) = 1 + length xs ⇒ length = foldr (/_ a -> 1 + a) 0

Ejercicio:

  1. Implemente map , filter , reverse , concat y concatMap recursivamente, al igual que las funciones anteriores en el lado izquierdo .

  2. Convierta estas 5 funciones a foldr según una fórmula anterior , es decir, sustituyendo f y v en la fórmula de plegado a la derecha .

Foldl a través de foldr

¿Cómo escribir una función recursiva que suma los números de izquierda a derecha?

sum [] = 0 -- given `sum [1,2,3]` expands into `(1 + (2 + 3))` sum (x:xs) = x + sum xs

La primera función recursiva que llega a encontrarse se expande por completo incluso antes de comenzar a sumar, eso no es lo que necesitamos. Un enfoque es crear una función recursiva que tenga acumulador , que suma números inmediatamente en cada paso (lea sobre recursividad final para aprender más sobre las estrategias de recursión):

suml :: [a] -> a suml xs = suml'' xs 0 where suml'' [] n = n -- auxiliary function suml'' (x:xs) n = suml'' xs (n+x)

Bien, para! Ejecuta este código en GHCi y asegúrate de que entiendes cómo funciona, luego, con cuidado y cuidado. suml no se puede redefinir con un fold, pero suml'' puede ser.

suml'' [] = v -- equivalent: v n = n suml'' (x:xs) n = f x (suml'' xs) n

suml'' [] n = n de la definición de la función, ¿verdad? Y v = suml'' [] de la fórmula de propiedad universal. Juntos esto da vn = n , una función que devuelve inmediatamente lo que recibe: v = id . Calculemos f :

suml'' (x:xs) n = f x (suml'' xs) n -- expand suml'' definition suml'' xs (n+x) = f x (suml'' xs) n -- replace `suml'' xs` with `g` g (n+x) = f x g n

Por lo tanto, suml'' = foldr (/xgn -> g (n+x)) id y, por lo tanto, suml = foldr (/xgn -> g (n+x)) id xs 0 .

foldr (/x g n -> g (n + x)) id [1..10] 0 -- return 55

Ahora solo tenemos que generalizar, reemplazar + por una función variable:

foldl f a xs = foldr (/x g n -> g (n `f` x)) id xs a foldl (-) 10 [1..5] -- returns -5

Conclusión

Ahora lea el tutorial de Graham Hutton sobre la universalidad y la expresividad del doblez . Coge papel y lápiz, intenta descifrar todo lo que escribe hasta que obtengas la mayoría de los pliegues por ti mismo. No te preocupes si no entiendes algo, siempre puedes regresar más tarde, pero tampoco postergues demasiado.