Folding across Maybes in Haskell

In an attempt to learn Haskell, I have come across a situation in which I wish to do a fold over a list but my accumulator is a Maybe. The function I'm folding with however takes in the "extracted" value in the Maybe and if one fails they all fail. I have a solution I find kludgy, but knowing as little Haskell as I do, I believe there should be a better way. Say we have the following toy problem: we want to sum a list, but fours for some reason are bad, so if we attempt to sum in a four at any time we want to return Nothing. My current solution is as follows:

import Maybe

explodingFourSum :: [Int] -> Maybe Int
explodingFourSum numberList =
    foldl explodingFourMonAdd (Just 0) numberList
    where explodingFourMonAdd =
        (\x y -> if isNothing x
                    then Nothing
                    else explodingFourAdd (fromJust x) y)

explodingFourAdd :: Int -> Int -> Maybe Int
explodingFourAdd _ 4 = Nothing
expl开发者_运维问答odingFourAdd x y = Just(x + y)

So basically, is there a way to clean up, or eliminate, the lambda in the explodingFourMonAdd using some kind of Monad fold? Or somehow currying in the >>= operator so that the fold behaves like a list of functions chained by >>=?

I think you can use foldM

explodingFourSum numberList = foldM explodingFourAdd 0 numberList

This lets you get rid of the extra lambda and that (Just 0) in the beggining.

BTW, check out hoogle to search around for functions you don't really remember the name for.

So basically, is there a way to clean up, or eliminate, the lambda in the explodingFourMonAdd using some kind of Monad fold?

Yapp. In Control.Monad there's the foldM function, which is exactly what you want here. So you can replace your call to foldl with foldM explodingFourAdd 0 numberList.

You can exploit the fact, that Maybe is a monad. The function sequence :: [m a] -> m [a] has the following effect, if m is Maybe: If all elements in the list are Just x for some x, the result is a list of all those justs. Otherwise, the result is Nothing.

So you first decide for all elements, whether it is a failure. For instance, take your example:

foursToNothing :: [Int] -> [Maybe Int]
foursToNothing = map go where
  go 4 = Nothing
  go x = Just x

Then you run sequence and fmap the fold:

explodingFourSum = fmap (foldl' (+) 0) . sequence . foursToNothing

Of course you have to adapt this to your specific case.

Here's another possibility not mentioned by other people. You can separately check for fours and do the sum:

import Control.Monad
explodingFourSum xs = guard (all (/=4) xs) >> return (sum xs)

That's the entire source. This solution is beautiful in a lot of ways: it reuses a lot of already-written code, and it nicely expresses the two important facts about the function (whereas the other solutions posted here mix those two facts up together).

Of course, there is at least one good reason not to use this implementation, as well. The other solutions mentioned here traverse the input list only once; this interacts nicely with the garbage collector, allowing only small portions of the list to be in memory at any given time. This solution, on the other hand, traverses xs twice, which will prevent the garbage collector from collecting the list during the first pass.

You can solve your toy example that way, too:

import Data.Traversable

explodingFour 4 = Nothing 
explodingFour x = Just x

explodingFourSum = fmap sum . traverse explodingFour 

Of course this works only because one value is enough to know when the calculation fails. If the failure condition depends on both values x and y in explodingFourSum, you need to use foldM.

BTW: A fancy way to write explodingFour would be

import Control.Monad

explodingFour x = mfilter (/=4) (Just x)

This trick works for explodingFourAdd as well, but is less readable:

explodingFourAdd x y = Just (x+) `ap` mfilter (/=4) (Just y)