One common example is using MonadPlus for some backtracking algorithm, then instantiatiating it to Maybe or List instance depending on wether you just want one solution or all of them.
Backtracking only works with the first kind, even if you're only interested in the first solution. This must hold:
(mplus a b) >>= c = mplus (a >>= c) (b >>= c)
Not really. If the recursive call is something like "msum [all_possible_paths]", then you are backtracking. The difference is that by using Maybe you'll stop as soon as you succeed, and with list you will find all possible paths. I don't have a small, self-contained, example at hand so I'll use one by Carsten Schultz that I once saw posted in comp.lang.functional. Hope he doesn't mind. http://groups-beta.google.com/group/comp.lang.functional/msg/d7ac1fe1684ef84... -- ------------------------------------------------------------------- -- knapsack problem module Subset2 where import Control.Monad sss :: MonadPlus m => Int -> [Int] -> m [Int] sss n [] | n>0 = mzero sss n (x:xs) = case compare n x of LT -> mzero EQ -> return [x] GT -> liftM (x:) (sss (n-x) xs) `mplus` sss n xs -- ------------------------------------------------------------------- sss 40 [3, 8, 9, 13, 14, 15, 17, 19] :: [[Int]] [[3,8,14,15],[3,9,13,15],[8,13,19],[8,15,17],[9,14,17]] sss 40 [3, 8, 9, 13, 14, 15, 17, 19] :: Maybe [Int] Just [3,8,14,15]
[*] For instance, I've missed Maybe being an instance of MonadError. You could define your own instance, of course.
Yes of course, and I did ;) But I think it should be provided nontheless, and I even find the fact that it isn't is playing a big part in all this confusion. Since there is no MonadError instance for Maybe, we end up using its MonadPlus instance, which just happens to be the same. But it cannot be generalized, for other types. Lets forget about lists, think (Either e). It's usual to move from (Maybe a) to (Either e a) to consider more than one kind of error. But, there is no natural instance of MonadPlus for (Either e a). What would mzero be? Yet, the "Maybe like, mplus operation" makes perfect sense in (Either e) or any other MonadError, though. You don't need Monoids at all, what you need is the concept of error. Just define it as: skipError x y = catchError x (\_->y) J.A.