What kind of knowledge or training is necessary for someone to write down the definition of foldlM like this?

Recently, I am trying to use Haskell in some of my real case production system. The Haskell type system really offers me great help. For example, when I realised that I need some function of type

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

There are actually functions like foldM, foldlM and foldrM.

However, what real shocked me is the definition of these functions, such as:

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

so function f' must be of type:

f' :: a -> b -> b

as required by foldr, then b must be of kind *-> m *, so the entire definition of foldlM could make sense.

Another example includes definitions of liftA2 and <*>

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

I tried some of my own solutions before peeking into the source code. But the gap is so huge that I don't think I could ever come up with this solution, no matter how many lines of code I will write in future.

So my question is, what kind of knowledge or which specific mathematics branch is necessary for someone to reasoning on such a highly abstracted level.

I know Category theory might offer some help and I've been following this great lecture for a long time and still working on it.

Solution

In general, logic etc., I would imagine. But you can also learn it by doing it. :) With time you notice some patterns, pick up some tricks.

Like this foldr with an extra argument thing. Some see it as folding into functions so they can be combined through . and id (which sometimes are really <=< and 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)
-}

Some find it easier to understand it in simpler, syntactical terms, as

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

so when g is non-strict in its second argument, s can serve as a state being passed along from the left, even though we're folding on the right, as one example.