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

Question

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.

Answer 1

So the best way to understand it is by doing it. Below there's an implementation of foldlM using foldl instead of foldr. It is a good excercise, try it and come later to the solution I'd suggest. The example explain all the reasoning I've done to achieve it, which might be different from yours, and might be bias because I've already knew about using a function accumulator.

Step 1: Let's try to write foldlM in terms of foldl

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

Here you realize that f' is pure and you'd need to extract the result of f to type match. The only way to 'extract' a monadic value is with >>= operator, but such an operator needs to be wrap right after it is used.

So as a conclusion: Every time you end up with I'd like to fully unwrap this monad, just give up. Is not the right way

Step 2: Let's try to write foldlM in terms of foldl but first using [] as foldable, since it is easy to pattern match (i.e. we don't actually need to use 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, that was easy. Let compare the definition with the usual foldl definition for lists

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

Cool!! they are pretty much the same. The trivial case is about the exact same thing. The recursive case is a little bit different, you'd like to write something more like: foldlM' f (f z0 x) xs. But is doesn't compile as in step 1, so you might think OK, I don't want to apply f, just to hold such a computation and compose it with >>=. I'd like to write something more like foldlM' f (f z0 x >>=) xs if it had sense...

Step 3 Realize that what you want to accumulate is a function composition and not a result. (here I am probably bias by the fact that I already knew it because you've posted it).

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. 

By the type of initFunc and using our knowledge from step 2 (the recursive definition) we can deduce that initFunc = return. The definition of f' can be completed knowing that f' should use f and >>=.

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

As you can see, it is not soooo difficult to do it. It needs practise, but I am not a professional haskell developer and I could do it myself, It is a matter of practise

Answer 2

You don't need any specific knowledge in mathematics to write a function like foldM. I'm using Haskell in production for 4 years already, and I'm also struggling with understanding this definition of foldM. But that is mostly because it's poorly written. Please, don't take it as a personal fault if you can't understand some obscure code. Here is a more readable version of foldlM

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

This function is still not the easiest one. Mostly because it has non-typical usage of foldr where the intermediate accumulator is a function. But you can see a few mays that make such definition more readable:

1. Comments about function arguments.
2. Better argument names (still short and idiomatic, but they are at least more readable).
3. The explicit type signature of the function inside where (so you know the shape of the arguments).

After seeing such function, you can now perform Equational reasoning technique to expand the definition step-by-step and see how it works. Ability to come up with such functions comes with experience. I don't have strong mathematician skills, and this function is not a typical Haskell function. But the more practice you have, the better it gets :)

Answer 3

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.