¿Qué tipo de conocimiento o capacitación es necesaria para que alguien escriba la definición de foldlM como esta? [cerrado]

Recientemente, estoy tratando de usar Haskell en algunos de mis sistemas de producción de casos reales. El sistema de tipos Haskell realmente me ofrece una gran ayuda. Por ejemplo, cuando me di cuenta de que necesitaba alguna función de tipo

f :: (Foldable t, Monad m) => ( a-> b -> m b) -> b -> t a -> m b

En realidad, hay funciones como foldM, foldlMy foldrM.

Sin embargo, lo que realmente me sorprendió es la definición de estas funciones, tales como:

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

entonces la función f'debe ser de tipo:

f' :: a -> b -> b

según lo requerido por foldr, entonces bdebe ser amable *-> m *, por lo que toda la definición de foldlMpodría tener sentido.

Otro ejemplo incluye definiciones de liftA2y<*>

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 id

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

Probé algunas de mis propias soluciones antes de mirar el código fuente. Pero la brecha es tan grande que no creo que pueda encontrar esta solución, sin importar cuántas líneas de código escriba en el futuro.

Entonces mi pregunta es, qué tipo de conocimiento o qué rama matemática específica es necesaria para que alguien razone en un nivel tan altamente abstracto.

Sé que la teoría de categorías podría ofrecer algo de ayuda y he estado siguiendo esta gran conferencia durante mucho tiempo y todavía estoy trabajando en ello.

En general, lógica, etc., me imagino. Pero también puedes aprenderlo haciéndolo. :) Con el tiempo notas algunos patrones, toma algunos trucos.

Me gusta esto foldrcon un argumento extra. Algunos lo ven como plegado en funciones para que puedan combinarse .y id(que a veces son realmente <=<y return),

foldr g z xs  =  foldr ($) z . map g $ xs
              =  foldr (.) id (map g xs) z
         ~/=  foldr (<=<) return (map g xs) z
{-
  (\f -> f . f) :: (a -> a) -> (a -> a)

  (\f -> f <=< f) :: Monad m => (a -> m a) -> (a -> m a)
                            (still just a type, not a kind)
-}

A algunos les resulta más fácil entenderlo en términos sintácticos más simples, como

foldr g z [a,b,c,...,n] s =
     g a (foldr g z [b,c,...,n]) s

entonces, cuando gno es estricto en su segundo argumento, spuede servir como un estado que se transmite desde la izquierda, aunque estemos doblando a la derecha, como un ejemplo.

Entonces, la mejor manera de entenderlo es hacerlo. A continuación hay una implementación de foldlMuso en foldllugar de foldr. Es un buen ejercicio, pruébalo y luego ve a la solución que sugeriría. El ejemplo explica todo el razonamiento que he hecho para lograrlo, que podría ser diferente al suyo y podría ser parcial porque ya sabía sobre el uso de un acumulador de funciones.

Paso 1 : tratemos de escribir foldlMen términos defoldl

-- this doesn't compile because f returning type is (m b) and not just (b) 
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f z0 xs 

-- So let substitute f by some undefined f'
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' z0 xs
  where f' = undefined

-- cool, but f' should use f somehow in order to get the monadic behaviour
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' z0 xs
  where f' b a = f somethingIDontkNow 

Aquí te das cuenta de que f'es puro y necesitarías extraer el resultado de fescribir coincidencia. La única forma de 'extraer' un valor monádico es con el >>=operador, pero dicho operador debe ajustarse inmediatamente después de su uso.

Como conclusión: cada vez que termines me gustaría desenvolver completamente esta mónada , solo ríndete. No es el camino correcto

Paso 2 : Intentemos escribir foldlMen términos de, foldlpero primero, usarlo []como plegable, ya que es fácil de combinar patrones (es decir, en realidad no necesitamos usar fold)

-- This is not very hard. It is pretty standard recursion schema. :)
foldlM' :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
foldlM' f z0 []     = return z0
foldlM' f z0 (x:xs) = f z0 x >>= \c -> foldlM' f c xs

Ok, eso fue fácil. Vamos a comparar la definición con la foldldefinición habitual para listas

foldlM' :: (Monad m) => (b -> a -> m b) -> b -> [a] -> m b
foldlM' f z0 []     = return z0
foldlM' f z0 (x:xs) = f z0 x >>= \c -> foldlM' f c xs

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

¡¡Frio!! Son más o menos lo mismo. El caso trivial es exactamente lo mismo. El caso recursivo es un poco diferente de bits, desea escribir algo más como: foldlM' f (f z0 x) xs. Pero no se compila como en el paso 1, por lo que puede pensar que está bien, no quiero aplicar f, solo para mantener dicho cálculo y componerlo >>=. Me gustaría escribir algo más como foldlM' f (f z0 x >>=) xs si tuviera sentido ...

Paso 3 Date cuenta de que lo que quieres acumular es una composición de funciones y no un resultado. ( Aquí probablemente soy parcial por el hecho de que ya lo sabía porque lo has publicado ).

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' initFunc xs
  where initFunc = undefined :: b -> m b
        f'       = undefined :: (b -> m b) -> a -> (b -> m b) -- This type signature can be deduce because f' should be applied to initFunc and a's from t a. 

Por el tipo initFuncy el uso de nuestro conocimiento del paso 2 (la definición recursiva) podemos deducir eso initFunc = return. La definición de f'se puede completar sabiendo que f'debe usar fy >>=.

foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldl f' return xs z0
--                        ^^^^^^
--                        |- Initial value
  where f' b a = \bvalue -> b bvalue >>= \bresult -> f bresult a -- this is equivalent to (b >=> \result -> f result a) which captures the sequence behaviour of the implementation
--         ^      ^^^^^^                  ^^^^^^^
--         |      |                       |- This is the result of previous computation
--         |      |- f' should return a function b -> m b. Any time you have to return a function, start writing a lambda  
--         |- This b is the accumulated value and has type b -> m b
-- Following the types you can write this with enough practise

Como puede ver, no es tan difícil hacerlo. Necesita práctica, pero no soy un desarrollador profesional de haskell y podría hacerlo yo mismo. Es una cuestión de práctica.

No necesitas ningún conocimiento específico en matemáticas para escribir una función como foldM. Estoy usando Haskell en producción durante 4 años, y también estoy luchando por comprender esta definición de foldM. Pero eso se debe principalmente a que está mal escrito. Por favor, no lo tome como una falta personal si no puede entender algún código oscuro. Aquí hay una versión más legible defoldlM

foldlM
    :: forall t m a b .
       (Foldable t, Monad m)
    => (b -> a -> m b)  -- ^ Monadic action
    -> b                -- ^ Starting accumulator
    -> t a              -- ^ List of values
    -> m b              -- ^ Computation result inside a monad
foldlM f z xs = (foldr step pure xs) z
  where
    step :: a -> (b -> m b) -> b -> m b
    step cur next acc = do
        result <- f acc cur
        next result

Esta función aún no es la más fácil. Principalmente porque tiene un uso no típico de foldrdonde el acumulador intermedio es una función. Pero puede ver algunos mays que hacen que dicha definición sea más legible:

1. Comentarios sobre argumentos de funciones.
2. Mejores nombres de argumentos (aún cortos e idiomáticos, pero al menos son más legibles).
3. La firma de tipo explícito de la función dentro where(para que conozca la forma de los argumentos).

Después de ver dicha función, ahora puede realizar una técnica de razonamiento equitativo para expandir la definición paso a paso y ver cómo funciona. La capacidad de crear tales funciones viene con experiencia. No tengo habilidades matemáticas fuertes, y esta función no es una función típica de Haskell. Pero cuanto más práctica tengas, mejor se pone :)