Lifting foldr to monad

Question

I have function smallStep :: Command -> Data -> Either StepError Data, and I would like to make bigStep :: [Command] -> Data -> Either StepError Data using it, with following semantic:

bigStep []   data   = Right data
bigStep c:cs data   = do
               data' <- bigStep cs data
               smallStep c data'

It's nothing convoluted, but if smallStep had type Command -> Data -> Data, I would implement bigStep simply as bigStep commands data = foldr data smallStep commands.

Naturally, I would like to use foldr here as well. How do I do this? foldM is lifted foldl, and reversing list doesn't sound like a terribly good idea.

Answer 1

In general, a left fold won't be better or worse than a right fold in terms of resource usage. However, I would assume that [Command] is supposed to be a list of sequenced commands intended to be executed one after another in the order they are supplied. If that is the case, it is probably easiest to build these lists backwards to begin with (instead of reversing them - this is indeed a costly operation for long lists). If you don't want to do that, here is a general monadic right fold:

foldrM :: Monad m => (a -> b -> m b) -> b -> [a] -> m b
foldrM f d []     = return d
foldrM f d (x:xs) = (\z -> f x z) =<< foldrM f d xs

Note the types of all the following :

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

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

We can deduce that foldrM is indeed a right fold.

However, if you need to fold a very large list, both of the monadic folds above are lazy and will only begin evaluation once the last function application is sequenced.