Escribir foldl usando foldr

Question 1

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

Escriba 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 alguien 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)

Alguien más, Jef G, hizo un excelente trabajo proporcionando un ejemplo y mostrando 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:

¿Para qué sirve la función id? ¿Cuál es el papel de? ¿Por qué deberíamos necesitarlo aquí?
En el ejemplo anterior, ¿la función id es el acumulador en la función lambda?
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!

Question 2

¡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í?

ides la función de identidad , id x = xy se utiliza como el equivalente de cero cuando la construcción de una cadena de funciones con la composición de funciones , (.). Puede 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 crea mediante la aplicación de funciones repetidas. No hay lambda explícita, ya que nombramos el acumulador, step. Puedes escribirlo con una lambda si quieres:

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

O como escribiría Graham Hutton :

5.1 El foldl operador

Ahora generalicemos del sumlejemplo y consideremos el operador estándar foldlque procesa los elementos de una lista en orden de izquierda a derecha usando una función fpara combinar valores y un valorv como valor inicial:
foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs
Con este operador, sumlse puede redefinir simplemente con suml = foldl (+) 0. Muchas otras funciones se pueden definir de forma sencilla utilizando foldl. Por ejemplo, la función estándar se reversepuede redefinir usando foldllo siguiente:
reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]
Esta definición es más eficiente que nuestra definición original usando fold, porque evita el uso del operador de adición ineficiente (++) para listas.

Una simple generalización del cálculo en la sección anterior para la función sumlmuestra cómo redefinir la función foldlen términos de fold:
foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v
Por el contrario, no es posible redefinir folden términos de foldl, debido al hecho de que foldles estricto en la cola de su argumento de lista pero foldno lo es. Hay una serie de 'teoremas de dualidad' útiles sobrefold y foldl, y también algunas pautas para decidir qué operador se adapta mejor a aplicaciones particulares (Bird, 1998).

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

Un programador de Haskell diría que el tipo de foldres(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 una mala pasada y reemplazamos el acumulador con una función, que a su vez se aplica al valor inicial para obtener un resultado.

Graham Hutton explica el truco para convertirse foldlen foldren el artículo anterior. Comenzamos por escribir 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 refactorice 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 gpara flotar vhacia adentro:

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

Que es lo mismo que pensar gen 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 guna función que recorre recursivamente una lista, aplica alguna función f. El valor final es la función de identidad, y cada paso también da como resultado una función.

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

2 El operador de plegado

El foldoperador tiene su origen en la teoría de la recursividad (Kleene, 1952), mientras que el uso de foldcomo concepto central en un lenguaje de programación se remonta al operador de reducción de APL (Iverson, 1962), y más tarde al operador de inserción de FP (Backus , 1978). En Haskell, el foldoperador de listas se puede definir de la siguiente manera:
fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)
Es decir, dada una función fde tipo α → β → βy un valor vde tipo β, la función fold f vprocesa una lista de tipo [α]para dar un valor de tipo βreemplazando el constructor nil []al final de la lista por el valor v, y cada constructor cons (:)dentro de la lista por la función f. De esta manera, el foldoperador encapsula un patrón simple de recursividad para procesar listas, en el que los dos constructores de listas simplemente se reemplazan por otros valores y funciones. Varias funciones familiares en listas tienen una definición simple usando fold.

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

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

si y solo si

g = fold f v

Entonces, la propiedad universal de los pliegues establece que:

    g = foldr k v

donde gdebe ser equivalente a las dos ecuaciones, para algunas ky v:

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

De nuestros diseños de pliegues anteriores, lo sabemos v == id. Sin embargo, para la segunda ecuación, 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 ky vproduce 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 recursivo gse reemplaza con el combinador plegable, y el acumulador se convierte en una función construida a través de una cadena de composiciones def en cada elemento de la lista, en orden inverso (por lo que doblamos a la izquierda en lugar de a la derecha).

Esto definitivamente es algo avanzado, por lo que para comprender 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

Wiki de Haskell: Foldl como foldr
Un tutorial sobre la universalidad y expresividad de fold , Graham Hutton, J. Functional Programming 9 (4): 355–372, julio de 1999.
Malcolm, G. Tipos de datos algebraicos y transformación de programas. , Tesis doctoral, Universidad de Groningen.

Question 3

Considere el tipo de foldr:

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

Mientras que el tipo de stepes algo así como b -> (a -> a) -> a -> a. Como se está pasando a step foldr, podemos concluir que en este caso el pliegue tiene un tipo como (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a).

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

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

En cuanto a steptomar 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? Se necesita 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 de la foldr: (foldr step id xs) z. La parte entre paréntesis es el propio pliegue, que devuelve una función, que luego se aplica a z.

Question 4

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

Propiedad universal de pliegue

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

Básicamente, si su función recursiva funciona en listas y se ve como a la izquierda , puede transformarla para doblar una a la derecha , sustituyendo fy vpor 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 = 0y sum (x:xs) = x + sum xses equivalente a sum (x:xs) = (+) x (sum xs), por 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:

Implementar map, filter, reverse, concaty concatMapde forma recursiva, al igual que las funciones anteriores en la izquierda lateral.

Convierta estas 5 funciones en foldr de acuerdo con la fórmula anterior , es decir, sustituyendo fy ven la fórmula de fold de la derecha .

Foldl a través de foldr

¿Cómo escribir una función recursiva que sume 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 encontrar se expande por completo incluso antes de que comience a sumar, eso no es lo que necesitamos. Un enfoque es crear una función recursiva que tenga un acumulador , que inmediatamente sume números en cada paso (lea sobre la recursividad de cola para obtener más información sobre las estrategias de recursividad):

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

¡Muy bien, detente! Ejecute este código en GHCi y asegúrese de comprender cómo funciona, luego proceda con cuidado y cuidado. sumlno se puede redefinir con un pliegue, pero suml'se puede.

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

suml' [] n = nde la definición de función, ¿verdad? Y v = suml' []de la fórmula de la propiedad universal. En conjunto, esto da v n = 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 (\x g n -> g (n+x)) idy por lo tanto suml = foldr (\x g n -> g (n+x)) id xs 0.

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

Ahora solo necesitamos 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 expresividad del pliegue . Consiga papel y lápiz, intente descifrar todo lo que escriba hasta que consiga derivar la mayoría de los pliegues por su cuenta. No te preocupes si no entiendes algo, siempre puedes volver más tarde, pero tampoco lo postergues mucho.

Question 5

Aquí está mi prueba que foldlse puede expresar en términos de foldr, que encuentro bastante simple, aparte del nombre espagueti stepque introduce la función.

La proposición es que foldl f z xses equivalente a

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

La primera cosa importante a notar aquí es que el lado derecho de la primera línea se evalúa realmente como

(foldr step_f id xs) z

ya que foldrsolo toma tres parámetros. Esto ya sugiere que foldrcalculará no un valor sino una función de curry, que luego se aplicará z. Hay dos casos a investigar para averiguar si myfoldles foldl:

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)

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

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

Question 6

No existe 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 h z? Asume eso 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 la definición de id:

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

Aplicar la definición de pliegue:

= foldl f z [x0, x1, x2]

¿Es un camino real o qué?

Question 7

Antes de votar en contra, lea el siguiente párrafo

Estoy publicando la respuesta para aquellas personas que podrían encontrar este enfoque más adecuado a su forma de pensar. La respuesta posiblemente contenga información y pensamientos redundantes, pero es lo que necesitaba para abordar el problema. Además, dado que esta es otra respuesta a la misma pregunta, es obvio que tiene superposiciones sustanciales con las otras respuestas, sin embargo, cuenta la historia de cómo podría comprender este concepto.

De hecho, comencé a escribir estas notas como un registro personal de mis pensamientos mientras trataba de comprender este tema. Me tomó todo el día tocar el núcleo, si es que realmente lo tengo.

Mi largo camino para comprender este sencillo ejercicio

Parte fácil: ¿qué debemos determinar?

¿Qué sucede con la siguiente llamada de ejemplo

foldl f z [1,2,3,4]

se puede visualizar con el siguiente diagrama (que está en Wikipedia , pero lo vi por primera vez en otra respuesta ):

          _____results in a number
         /
        f          f (f (f (f z 1) 2) 3) 4
       / \
      f   4        f (f (f z 1) 2) 3
     / \
    f   3          f (f z 1) 2
   / \
  f   2            f z 1
 / \
z   1

(Como nota al margen, al usar foldl cada aplicación de fno se realiza, y las expresiones se procesan tal como las escribí anteriormente; en principio, podrían calcularse a medida que avanza desde abajo hacia arriba, y eso es exactamente lo quefoldl' hace).

El ejercicio esencialmente nos desafía a usar en foldrlugar de foldlcambiar apropiadamente la función de paso (así que usamoss lugar de f) y el acumulador inicial (por lo que usamos en ?lugar dez ); la lista permanece igual, de lo contrario, ¿de qué estamos hablando?

La llamada a foldr tiene que verse así:

foldr s ? [1,2,3,4]

y el diagrama correspondiente es este:

    _____what does the last call return?
   /
  s
 / \
1   s
   / \
  2   s
     / \
    3   s
       / \
      4   ? <--- what is the initial accumulator?

La llamada resulta en

s 1 (s 2 (s 3 (s 4 ?)))

¿Qué son sy ?? ¿Y cuáles son sus tipos? Parece sque es una función de dos argumentos, muy parecida f, pero no saquemos conclusiones precipitadas. Además, dejemos ?a un lado por un momento, y observemos que ztiene que entrar en juego en cuanto 1entra en juego; sin embargo, ¿cómo puede zentrar en juego en la llamada a la función quizás-dos-argumentos s, es decir, en la llamada s 1 (…)? Podemos resolver esta parte del enigma eligiendo una sque tome 3 argumentos, en lugar de los 2 que mencionamos anteriormente, de modo que la llamada más externas 1 (…) resultará en una función que tome un argumento, ¡al que podemos pasar z!

Esto significa que queremos la llamada original, que se expande a

f (f (f (f z 1) 2) 3) 4

ser equivalente a

s 1 (s 2 (s 3 (s 4 ?))) z

o, en otras palabras, queremos que la función aplicada parcialmente

s 1 (s 2 (s 3 (s 4 ?)))

para ser equivalente a la siguiente función lambda

(\z -> f (f (f (f z 1) 2) 3) 4)

De nuevo, las "únicas" piezas que necesitamos son sy ?.

Punto de inflexión: reconocer la composición de la función

Rediseñemos el diagrama anterior y escribamos a la derecha a qué queremos que ssea equivalente cada llamada :

  s          s 1 (…) == (\z -> f (f (f (f z 1) 2) 3) 4)
 / \
1   s        s 2 (…) == (\z -> f (f (f    z    2) 3) 4)
   / \
  2   s      s 3 (…) == (\z -> f (f       z       3) 4)
     / \
    3   s    s 4  ?  == (\z -> f          z          4)
       / \
      4   ? <--- what is the initial accumulator?

Espero que quede claro por la estructura del diagrama que (…)en cada línea está el lado derecho de la línea debajo de ella; mejor, es la función devuelta de la llamada anterior (a continuación) a s.

También debe quedar claro que una llamada a scon argumentos xy yes la aplicación (completa) de ya la aplicación parcial de fal único argumento x. Dado que la aplicación parcial de fa xse puede escribir como la lambda (\z -> f z x), aplicando totalmente ya él resulta en la lambda (\z -> y (f z x)), que en este caso me gustaría reescribir como y . (\z -> f z x); traducir las palabras en una expresión paras obtener

s x y = y . (\z -> f z x)

(Esto es lo mismo que s x y z = y (f z x) , que es lo mismo que el libro, si cambia el nombre de las variables).

El último bit es: ¿cuál es el "valor" inicial? del acumulador? El diagrama anterior se puede reescribir expandiendo las llamadas anidadas para convertirlas en cadenas de composición:

  s          s 1 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4  ?  == (\z -> f z 4)
       / \
      4   ? <--- what is the initial accumulator?

Aquí vemos que ssimplemente "acumula" sucesivas aplicaciones parciales de f, pero lay en s x y = y . (\z -> f z x)sugiere que la interpretacións 4 ? (y, a su vez, todas las demás) pierde una función principal que se compondrá con la lambda más a la izquierda.

Esa es solo nuestra ?función: es el momento de darle una razón de su existencia, además de ocupar un lugar en la llamada a foldr. ¿Qué podemos elegir que sea para no cambiar las funciones resultantes? Respuesta:, idel elemento de identidad con respecto al operador de composición (.).

  s          s 1 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == id . (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4 id  == id . (\z -> f z 4)
       / \
      4   id

Entonces la función buscada es

myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z

Question 8

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

Question 9

foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero []        = zero

myFold f z xs = foldr step id xs z
  where step x g a = g (f a x)

myFold (+) 0 [1, 2, 3] =
  foldr step id [1, 2, 3] 0
  -- Expanding foldr function
  step 1 (foldr step id [2, 3]) 0
  step 1 (step 2 (foldr step id [3])) 0
  step 1 (step 2 (step 3 (foldr step id []))) 0
  -- Expanding step function if it is possible
  step 1 (step 2 (step 3 id)) 0
  step 2 (step 3 id) (0 + 1)
  step 3 id ((0 + 1) + 2)
  id (((0 + 1) + 2) + 3)

Bueno, al menos esto me ayudó. Incluso no está del todo bien.

Question 10

Esta respuesta hace que la definición a continuación se entienda fácilmente en tres pasos.

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

Paso 1. transformar el pliegue de la evaluación de funciones en una combinación de funciones

foldl f z [x1 .. xn] = z & f1 & .. & fn = fn . .. . f1 z. en el cualfi = \z -> f z xi .

(Al usarlo z & f1 & f2 & .. & fnsignifica fn ( .. (f2 (f1 z)) .. ).)

Paso 2. expresar la combinación de funciones de una foldrmanera

foldr (.) id [f1 .. fn] = (.) f1 (foldr (.) id [f2 .. fn]) = f1 . (foldr (.) id [f2 .. fn]). Desdobla el resto para conseguirlo foldr (.) id [f1 .. fn] = f1 . .. . fn.

Al notar que la secuencia se invierte, debemos usar la forma invertida de (.). rc f1 f2 = (.) f2 f1 = f2 . f1Entonces, defina foldr rc id [f1 .. fn] = rc f1 (foldr (.) id [f2 .. fn]) = (foldr (.) id [f2 .. fn]) . f1. Desdobla el resto para conseguirlo foldr rc id [f1 .. fn] = fn . .. . f1.

Paso 3. transformar la lista de funciones de plegado en la lista de operandos de plegado

Encuentra stepque hace foldr step id [x1 .. xn] = foldr rc id [f1 .. fn]. Es fácil de encontrar step = \x g z -> g (f z x).

En 3 pasos, la definición de foldluso foldres clara:

  foldl f z xs
= fn . .. . f1 z
= foldr rc id fs z
= foldr step id xs z

Demuestre la exactitud:

foldl f z xs = foldr (\x g z -> g (f z x)) id xs z
             = step x1 (foldr step id [x2 .. xn]) z
             = s1 (foldr step id [x2 .. xn]) z
             = s1 (step x2 (foldr step id [x3 .. xn])) z
             = s1 (s2 (foldr step id [x3 .. xn])) z
             = ..
             = s1 (s2 (.. (sn (foldr step id [])) .. )) z
             = s1 (s2 (.. (sn id) .. )) z
             = (s2 (.. (sn id) .. )) (f z x1)
             = s2 (s3 (.. (sn id) .. )) (f z x1)
             = (s3 (.. (sn id) .. )) (f (f z x1) x2)
             = ..
             = sn id (f (.. (f (f z x1) x2) .. ) xn-1)
             = id (f (.. (f (f z x1) x2) .. ) xn)
             = f (.. (f (f z x1) x2) .. ) xn

in which xs = [x1 .. xn], si = step xi = \g z -> g (f z xi)

Si encuentra algo que no está claro, agregue un comentario. :)

Answer 1

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

Escriba 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 alguien 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)

Alguien más, Jef G, hizo un excelente trabajo proporcionando un ejemplo y mostrando 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:

¿Para qué sirve la función id? ¿Cuál es el papel de? ¿Por qué deberíamos necesitarlo aquí?
En el ejemplo anterior, ¿la función id es el acumulador en la función lambda?
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!

Answer 2

2

Para el masoquista real,step = curry $ uncurry (&) <<< (flip f) *** (.)

Weijun Zhou

Answer 3

¡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í?

ides la función de identidad , id x = xy se utiliza como el equivalente de cero cuando la construcción de una cadena de funciones con la composición de funciones , (.). Puede 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 crea mediante la aplicación de funciones repetidas. No hay lambda explícita, ya que nombramos el acumulador, step. Puedes escribirlo con una lambda si quieres:

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

O como escribiría Graham Hutton :

5.1 El foldl operador

Ahora generalicemos del sumlejemplo y consideremos el operador estándar foldlque procesa los elementos de una lista en orden de izquierda a derecha usando una función fpara combinar valores y un valorv como valor inicial:
foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs
Con este operador, sumlse puede redefinir simplemente con suml = foldl (+) 0. Muchas otras funciones se pueden definir de forma sencilla utilizando foldl. Por ejemplo, la función estándar se reversepuede redefinir usando foldllo siguiente:
reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]
Esta definición es más eficiente que nuestra definición original usando fold, porque evita el uso del operador de adición ineficiente (++) para listas.

Una simple generalización del cálculo en la sección anterior para la función sumlmuestra cómo redefinir la función foldlen términos de fold:
foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v
Por el contrario, no es posible redefinir folden términos de foldl, debido al hecho de que foldles estricto en la cola de su argumento de lista pero foldno lo es. Hay una serie de 'teoremas de dualidad' útiles sobrefold y foldl, y también algunas pautas para decidir qué operador se adapta mejor a aplicaciones particulares (Bird, 1998).

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

Un programador de Haskell diría que el tipo de foldres(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 una mala pasada y reemplazamos el acumulador con una función, que a su vez se aplica al valor inicial para obtener un resultado.

Graham Hutton explica el truco para convertirse foldlen foldren el artículo anterior. Comenzamos por escribir 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 refactorice 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 gpara flotar vhacia adentro:

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

Que es lo mismo que pensar gen 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 guna función que recorre recursivamente una lista, aplica alguna función f. El valor final es la función de identidad, y cada paso también da como resultado una función.

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

2 El operador de plegado

El foldoperador tiene su origen en la teoría de la recursividad (Kleene, 1952), mientras que el uso de foldcomo concepto central en un lenguaje de programación se remonta al operador de reducción de APL (Iverson, 1962), y más tarde al operador de inserción de FP (Backus , 1978). En Haskell, el foldoperador de listas se puede definir de la siguiente manera:
fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)
Es decir, dada una función fde tipo α → β → βy un valor vde tipo β, la función fold f vprocesa una lista de tipo [α]para dar un valor de tipo βreemplazando el constructor nil []al final de la lista por el valor v, y cada constructor cons (:)dentro de la lista por la función f. De esta manera, el foldoperador encapsula un patrón simple de recursividad para procesar listas, en el que los dos constructores de listas simplemente se reemplazan por otros valores y funciones. Varias funciones familiares en listas tienen una definición simple usando fold.

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

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

si y solo si

g = fold f v

Entonces, la propiedad universal de los pliegues establece que:

    g = foldr k v

donde gdebe ser equivalente a las dos ecuaciones, para algunas ky v:

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

De nuestros diseños de pliegues anteriores, lo sabemos v == id. Sin embargo, para la segunda ecuación, 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 ky vproduce 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 recursivo gse reemplaza con el combinador plegable, y el acumulador se convierte en una función construida a través de una cadena de composiciones def en cada elemento de la lista, en orden inverso (por lo que doblamos a la izquierda en lugar de a la derecha).

Esto definitivamente es algo avanzado, por lo que para comprender 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

Wiki de Haskell: Foldl como foldr
Un tutorial sobre la universalidad y expresividad de fold , Graham Hutton, J. Functional Programming 9 (4): 355–372, julio de 1999.
Malcolm, G. Tipos de datos algebraicos y transformación de programas. , Tesis doctoral, Universidad de Groningen.

Answer 4

1

Por favor, corrija el error tipográfico en k = \x g' -> (\a -> g' (f v x)) y(\x g -> (\a -> g (f v x)))

Kamel

Answer 5

Considere el tipo de foldr:

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

Mientras que el tipo de stepes algo así como b -> (a -> a) -> a -> a. Como se está pasando a step foldr, podemos concluir que en este caso el pliegue tiene un tipo como (b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a).

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

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

En cuanto a steptomar 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? Se necesita 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 de la foldr: (foldr step id xs) z. La parte entre paréntesis es el propio pliegue, que devuelve una función, que luego se aplica a z.

Answer 6

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

Propiedad universal de pliegue

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

Básicamente, si su función recursiva funciona en listas y se ve como a la izquierda , puede transformarla para doblar una a la derecha , sustituyendo fy vpor 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 = 0y sum (x:xs) = x + sum xses equivalente a sum (x:xs) = (+) x (sum xs), por 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:

Implementar map, filter, reverse, concaty concatMapde forma recursiva, al igual que las funciones anteriores en la izquierda lateral.

Convierta estas 5 funciones en foldr de acuerdo con la fórmula anterior , es decir, sustituyendo fy ven la fórmula de fold de la derecha .

Foldl a través de foldr

¿Cómo escribir una función recursiva que sume 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 encontrar se expande por completo incluso antes de que comience a sumar, eso no es lo que necesitamos. Un enfoque es crear una función recursiva que tenga un acumulador , que inmediatamente sume números en cada paso (lea sobre la recursividad de cola para obtener más información sobre las estrategias de recursividad):

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

¡Muy bien, detente! Ejecute este código en GHCi y asegúrese de comprender cómo funciona, luego proceda con cuidado y cuidado. sumlno se puede redefinir con un pliegue, pero suml'se puede.

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

suml' [] n = nde la definición de función, ¿verdad? Y v = suml' []de la fórmula de la propiedad universal. En conjunto, esto da v n = 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 (\x g n -> g (n+x)) idy por lo tanto suml = foldr (\x g n -> g (n+x)) id xs 0.

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

Ahora solo necesitamos 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 expresividad del pliegue . Consiga papel y lápiz, intente descifrar todo lo que escriba hasta que consiga derivar la mayoría de los pliegues por su cuenta. No te preocupes si no entiendes algo, siempre puedes volver más tarde, pero tampoco lo postergues mucho.

Answer 7

Encuentro esta respuesta más simple y clara que la aceptada. Lástima que tenga tan pocos votos

positivos

Answer 8

Aquí está mi prueba que foldlse puede expresar en términos de foldr, que encuentro bastante simple, aparte del nombre espagueti stepque introduce la función.

La proposición es que foldl f z xses equivalente a

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

La primera cosa importante a notar aquí es que el lado derecho de la primera línea se evalúa realmente como

(foldr step_f id xs) z

ya que foldrsolo toma tres parámetros. Esto ya sugiere que foldrcalculará no un valor sino una función de curry, que luego se aplicará z. Hay dos casos a investigar para averiguar si myfoldles foldl:

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)

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

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

Answer 9

No existe 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 h z? Asume eso 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 la definición de id:

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

Aplicar la definición de pliegue:

= foldl f z [x0, x1, x2]

¿Es un camino real o qué?

Answer 10

Antes de votar en contra, lea el siguiente párrafo

Estoy publicando la respuesta para aquellas personas que podrían encontrar este enfoque más adecuado a su forma de pensar. La respuesta posiblemente contenga información y pensamientos redundantes, pero es lo que necesitaba para abordar el problema. Además, dado que esta es otra respuesta a la misma pregunta, es obvio que tiene superposiciones sustanciales con las otras respuestas, sin embargo, cuenta la historia de cómo podría comprender este concepto.

De hecho, comencé a escribir estas notas como un registro personal de mis pensamientos mientras trataba de comprender este tema. Me tomó todo el día tocar el núcleo, si es que realmente lo tengo.

Mi largo camino para comprender este sencillo ejercicio

Parte fácil: ¿qué debemos determinar?

¿Qué sucede con la siguiente llamada de ejemplo

foldl f z [1,2,3,4]

se puede visualizar con el siguiente diagrama (que está en Wikipedia , pero lo vi por primera vez en otra respuesta ):

          _____results in a number
         /
        f          f (f (f (f z 1) 2) 3) 4
       / \
      f   4        f (f (f z 1) 2) 3
     / \
    f   3          f (f z 1) 2
   / \
  f   2            f z 1
 / \
z   1

(Como nota al margen, al usar foldl cada aplicación de fno se realiza, y las expresiones se procesan tal como las escribí anteriormente; en principio, podrían calcularse a medida que avanza desde abajo hacia arriba, y eso es exactamente lo quefoldl' hace).

El ejercicio esencialmente nos desafía a usar en foldrlugar de foldlcambiar apropiadamente la función de paso (así que usamoss lugar de f) y el acumulador inicial (por lo que usamos en ?lugar dez ); la lista permanece igual, de lo contrario, ¿de qué estamos hablando?

La llamada a foldr tiene que verse así:

foldr s ? [1,2,3,4]

y el diagrama correspondiente es este:

    _____what does the last call return?
   /
  s
 / \
1   s
   / \
  2   s
     / \
    3   s
       / \
      4   ? <--- what is the initial accumulator?

La llamada resulta en

s 1 (s 2 (s 3 (s 4 ?)))

¿Qué son sy ?? ¿Y cuáles son sus tipos? Parece sque es una función de dos argumentos, muy parecida f, pero no saquemos conclusiones precipitadas. Además, dejemos ?a un lado por un momento, y observemos que ztiene que entrar en juego en cuanto 1entra en juego; sin embargo, ¿cómo puede zentrar en juego en la llamada a la función quizás-dos-argumentos s, es decir, en la llamada s 1 (…)? Podemos resolver esta parte del enigma eligiendo una sque tome 3 argumentos, en lugar de los 2 que mencionamos anteriormente, de modo que la llamada más externas 1 (…) resultará en una función que tome un argumento, ¡al que podemos pasar z!

Esto significa que queremos la llamada original, que se expande a

f (f (f (f z 1) 2) 3) 4

ser equivalente a

s 1 (s 2 (s 3 (s 4 ?))) z

o, en otras palabras, queremos que la función aplicada parcialmente

s 1 (s 2 (s 3 (s 4 ?)))

para ser equivalente a la siguiente función lambda

(\z -> f (f (f (f z 1) 2) 3) 4)

De nuevo, las "únicas" piezas que necesitamos son sy ?.

Punto de inflexión: reconocer la composición de la función

Rediseñemos el diagrama anterior y escribamos a la derecha a qué queremos que ssea equivalente cada llamada :

  s          s 1 (…) == (\z -> f (f (f (f z 1) 2) 3) 4)
 / \
1   s        s 2 (…) == (\z -> f (f (f    z    2) 3) 4)
   / \
  2   s      s 3 (…) == (\z -> f (f       z       3) 4)
     / \
    3   s    s 4  ?  == (\z -> f          z          4)
       / \
      4   ? <--- what is the initial accumulator?

Espero que quede claro por la estructura del diagrama que (…)en cada línea está el lado derecho de la línea debajo de ella; mejor, es la función devuelta de la llamada anterior (a continuación) a s.

También debe quedar claro que una llamada a scon argumentos xy yes la aplicación (completa) de ya la aplicación parcial de fal único argumento x. Dado que la aplicación parcial de fa xse puede escribir como la lambda (\z -> f z x), aplicando totalmente ya él resulta en la lambda (\z -> y (f z x)), que en este caso me gustaría reescribir como y . (\z -> f z x); traducir las palabras en una expresión paras obtener

s x y = y . (\z -> f z x)

(Esto es lo mismo que s x y z = y (f z x) , que es lo mismo que el libro, si cambia el nombre de las variables).

El último bit es: ¿cuál es el "valor" inicial? del acumulador? El diagrama anterior se puede reescribir expandiendo las llamadas anidadas para convertirlas en cadenas de composición:

  s          s 1 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4  ?  == (\z -> f z 4)
       / \
      4   ? <--- what is the initial accumulator?

Aquí vemos que ssimplemente "acumula" sucesivas aplicaciones parciales de f, pero lay en s x y = y . (\z -> f z x)sugiere que la interpretacións 4 ? (y, a su vez, todas las demás) pierde una función principal que se compondrá con la lambda más a la izquierda.

Esa es solo nuestra ?función: es el momento de darle una razón de su existencia, además de ocupar un lugar en la llamada a foldr. ¿Qué podemos elegir que sea para no cambiar las funciones resultantes? Respuesta:, idel elemento de identidad con respecto al operador de composición (.).

  s          s 1 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1)
 / \
1   s        s 2 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2)
   / \
  2   s      s 3 (…) == id . (\z -> f z 4) . (\z -> f z 3)
     / \
    3   s    s 4 id  == id . (\z -> f z 4)
       / \
      4   id

Entonces la función buscada es

myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z

Answer 11

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

Answer 12

foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero []        = zero

myFold f z xs = foldr step id xs z
  where step x g a = g (f a x)

myFold (+) 0 [1, 2, 3] =
  foldr step id [1, 2, 3] 0
  -- Expanding foldr function
  step 1 (foldr step id [2, 3]) 0
  step 1 (step 2 (foldr step id [3])) 0
  step 1 (step 2 (step 3 (foldr step id []))) 0
  -- Expanding step function if it is possible
  step 1 (step 2 (step 3 id)) 0
  step 2 (step 3 id) (0 + 1)
  step 3 id ((0 + 1) + 2)
  id (((0 + 1) + 2) + 3)

Bueno, al menos esto me ayudó. Incluso no está del todo bien.

Answer 13

la secuencia real es foldr step id [1, 2, 3] 0-> step 1 (foldr step id [2, 3]) 0-> (foldr step id [2, 3]) (0 + 1)-> step 2 (foldr step id [3]) (0 + 1)-> (foldr step id [3]) ((0 + 1) + 2)-> step 3 (foldr step id []) ((0 + 1) + 2)-> (foldr step id []) (((0 + 1) + 2) + 3)-> id (((0 + 1) + 2) + 3).

Will Ness

Answer 14

Esta respuesta hace que la definición a continuación se entienda fácilmente en tres pasos.

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