[Haskell-beginners] State Monad vs. fold

[John Wiegley]

>>>>> martin  <martin.drautzburg at web.de> writes:

> Can someone give me some insights when the State Monad is beneficial and
> where a fold is the better choice.

Looking at the type of a fold:

    foldr :: (a -> b -> b) -> b -> [a] -> b

If we juggle the arguments we get:

    foldr :: (a -> b -> b) -> [a] -> b -> b

And if we imagine State b () actions, we can directly rewrite this as:

    foldrS :: (a -> State b ()) -> [a] -> State b ()

Which generalizes to:

    foldrS :: MonadState b m => (a -> m ()) -> [a] -> m ()

Which is roughly the same thing as using mapM_ over our State monad:

    mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

In other words, these two forms in our example say the same thing:

    foldr f b xs
    execState (mapM_ f' xs) b

With the only difference being the types of f and f':

    f  : a -> b -> b
    f' : a -> State b ()

The other question you asked is when to choose one over the other.  Since they
are equivalent, it's really up to you.  I tend to prefer using a fold over
State, to keep things on the level of functions and values, rather than
pulling in monads and possibly monad transformers unnecessarily.

But it's a very good thing to hold these isomorphisms in your mind, since you
can then freely switch from one representation to another as need be.  This is
true of a lot of type equivalences throughout Haskell, where the more things
you can see as being essentially the same, the more freedom you have to find
the best abstraction for a particular context.

John