Estoy tratando de crear foldl usando foldr (un buen ejercicio para aprender Haskell, y las otras respuestas parecen complejas).

Mis soluciones son esto:

myFoldl :: (b -> a -> b) -> [a] -> (b -> b)
myFoldl f = foldr op z
  where
    z = []
    op x xs b = myFoldl f xs (f b x)

Pero no funciona. Recibo un error que dice:

• Couldn't match type ‘a -> b’ with ‘[a]’
  Expected type: b -> (a -> b) -> a -> b
    Actual type: b -> [a] -> a -> b
• In the first argument of ‘foldr’, namely ‘op’
  In the expression: foldr op z
  In an equation for ‘myFoldl’:
      myFoldl f
        = foldr op z
        where
            z = []
            op x xs b = myFoldl f xs (f x b)

Pero me parece bien. myFoldl toma una función, una lista y algo con lo que trabajar. ¿Por qué esto no funciona? (Nuevo en Haskell, todavía tratando de resolverlo todo).

2
user2719875 13 jul. 2019 a las 18:27

1 respuesta

La mejor respuesta

Ya que tienes:

myFoldl f = foldr op z

También debes tener:

myFoldl f xs = foldr op z xs                  -- (**)

Desde el tipo de myFoldl, el LHS debe tener tipo b -> b. Por otro lado, desde el tipo de foldr, el RHS tiene el mismo tipo que z, que definió como z = [] que tiene un tipo de lista, [c]. Por lo tanto, esta expresión tiene el tipo b -> b, pero también el tipo de lista [c], y estos dos tipos no pueden reconciliarse.

El problema más grande es que su op no debe definirse recursivamente en términos de myFoldl. El punto del pliegue (ya sea a la izquierda o hacia la derecha) es para reemplazar la recursión explícita, abstraiendo el patrón de recursión como la definición de pliegue, expresándola con la operación de recombinación de un paso op x r = ... donde r es el resultado del sub-problema recursivo del problema, ya calculado para nosotros por el pliegue. Una definición correcta de la operación de recombinación de un paso, por lo tanto, no debe involucrar ninguna definición recursiva.

SOOOOO, déjame intentar establecerte en el camino correcto. Creo que ha reconocido que la relación recursiva definitoria para su myFoldl es:

myFoldl f (x:xs) b = myFoldl f xs (f b x)     -- (1a)
myFoldl f []     b = b                        -- (1b)

Uso de la definición (**) anterior, desea reconciliarlo con la relación recursiva definitoria para foldr:

foldr op z (x:xs) = op x (foldr op z xs)
foldr op z []     = z

Que podríamos extrear ETA sobre b así:

foldr op z (x:xs) b = op x (foldr op z xs) b  -- (2a)
foldr op z []     b = z b                     -- (2b)

Tenga en cuenta que la única forma (1b) y (2b) van a dar el mismo resultado es si b y z b son iguales para todos b. Tenga en cuenta que z es una función aquí, ¡no es una lista! Con suerte, puede identificar de inmediato qué función debe estar aquí.

Para conciliar (1A) y (2a), su solución fue escribir op x xs b = myFoldl f xs (f b x), pero esa no es la ecuación correcta. La ecuación correcta, que coincide con el RHSS de (1A) y (2a) anterior es:

op x (foldr op z xs) b = myFoldl f xs (f b x)

Y reescribiendo el foldr a la izquierda en términos de nuestro myFoldl usando (**) arriba arriba, obtenemos:

op x (myFoldl f xs) b = myFoldl f xs (f b x)

Ahora, ¿puede ver qué definición no recursiva de la operación de recombinación de un paso op satisfará esta ecuación? (Pista: Es una definición muy simple.)

op x r              b = ....
4
Will Ness 14 jul. 2019 a las 07:22