Que tipo de conhecimento ou treinamento é necessário para alguém escrever a definição de foldlM como esta? [fechadas]

Recentemente, estou tentando usar o Haskell em alguns dos meus sistemas de produção de casos reais. O sistema do tipo Haskell realmente me oferece uma grande ajuda. Por exemplo, quando percebi que preciso de alguma função do tipo

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

Na verdade, existem funções como foldM, foldlMe foldrM.

No entanto, o que realmente me chocou é a definição dessas funções, 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

portanto, a função f'deve ser do tipo:

f' :: a -> b -> b

conforme exigido por foldr, então bdeve ser do tipo *-> m *, para que toda a definição de foldlMfaça sentido.

Outro exemplo inclui definições de liftA2e<*>

(<*>) :: 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)

Eu tentei algumas das minhas próprias soluções antes de espreitar o código fonte. Mas a diferença é tão grande que acho que nunca poderia encontrar essa solução, independentemente de quantas linhas de código escreverei no futuro.

Portanto, minha pergunta é: que tipo de conhecimento ou qual ramo específico da matemática é necessário para alguém raciocinar em um nível tão abstrato.

Eu sei que a teoria das categorias pode oferecer alguma ajuda e eu acompanho esta ótima palestra há muito tempo e ainda estou trabalhando nela.

Em geral, lógica etc., eu imaginaria. Mas você também pode aprender fazendo isso. :) Com o tempo, você percebe alguns padrões, aprenda alguns truques.

Assim foldrcom um argumento extra. Alguns vêem isso como dobrar em funções para que possam ser combinadas .e id(que às vezes são reais <=<e 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)
-}

Alguns acham mais fácil entendê-lo em termos mais simples e sintáticos, como

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

portanto, quando gnão for rigoroso em seu segundo argumento, spode servir como um estado transmitido da esquerda, embora estejamos dobrando à direita, como um exemplo.

Portanto, a melhor maneira de entender é fazendo isso. Abaixo há uma implementação de foldlMusar em foldlvez de foldr. É um bom exercício, tente e chegue mais tarde à solução que eu sugiro. O exemplo explica todo o raciocínio que eu fiz para alcançá-lo, que pode ser diferente do seu e pode ser tendencioso, porque eu já sabia sobre o uso de um acumulador de funções.

Etapa 1 : vamos tentar escrever foldlMem termos 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 

Aqui você percebe que isso f'é puro e precisa extrair o resultado fpara digitar match. A única maneira de 'extrair' um valor monádico é com o >>=operador, mas esse operador precisa ser quebrado logo após ser usado.

Então, como conclusão: toda vez que você terminar, eu gostaria de desembrulhar completamente essa mônada , desista. Não é o caminho certo

Etapa 2 : vamos tentar escrever foldlMem termos de, foldlmas primeiro usar []como dobrável, já que é fácil padronizar a correspondência (ou seja, na verdade, não precisamos 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, isso foi fácil. Vamos comparar a definição com a foldldefinição usual 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

Legal!! eles são praticamente iguais. O caso trivial é exatamente a mesma coisa. O caso recursivo é um pouco diferente, você gostaria de escrever algo mais parecido com: foldlM' f (f z0 x) xs. Mas não é compilado como na etapa 1, então você pode pensar OK, não quero aplicar f, apenas para manter tal cálculo e compor com ele >>=. Eu gostaria de escrever algo mais como foldlM' f (f z0 x >>=) xs se tivesse sentido ...

Etapa 3 Perceba que o que você deseja acumular é uma composição de função e não um resultado. ( aqui estou provavelmente tendencioso pelo fato de já saber porque você o postou ).

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. 

Pelo tipo initFunce uso de nosso conhecimento da etapa 2 (a definição recursiva), podemos deduzir isso initFunc = return. A definição de f'pode ser concluída sabendo que f'deve usar fe >>=.

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 você pode ver, não é tão difícil fazê-lo. Precisa de prática, mas não sou um desenvolvedor profissional de haskell e poderia fazer isso sozinho, é uma questão de prática

Você não precisa de nenhum conhecimento específico em matemática para escrever uma função como foldM. Estou usando Haskell em produção há 4 anos e também estou lutando para entender essa definição de foldM. Mas isso é principalmente porque está mal escrito. Por favor, não tome isso como uma falha pessoal se você não conseguir entender algum código obscuro. Aqui está uma versão mais legível dofoldlM

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 função ainda não é a mais fácil. Principalmente porque tem uso não típico de foldronde o acumulador intermediário é uma função. Mas você pode ver alguns exemplos que tornam essa definição mais legível:

1. Comentários sobre argumentos de função.
2. Melhores nomes de argumento (ainda curtos e idiomáticos, mas são pelo menos mais legíveis).
3. A assinatura de tipo explícita da função dentro where(para que você saiba a forma dos argumentos).

Depois de ver essa função, agora você pode executar a técnica de raciocínio equacional para expandir a definição passo a passo e ver como ela funciona. A capacidade de criar essas funções vem com a experiência. Não tenho fortes habilidades matemáticas e essa função não é uma função típica de Haskell. Mas quanto mais prática você tiver, melhor fica :)