Learn You a Haskell for Great Good! - Miran Lipovaca [151]
10 is too large, throwing it away
Keeping 3
So, just by providing a monadic predicate to filterM, we were able to filter a list while taking advantage of the monadic context that we used.
A very cool Haskell trick is using filterM to get the powerset of a list (if we think of them as sets for now). The powerset of some set is a set of all subsets of that set. So if we have a set like [1,2,3], its powerset includes the following sets:
[1,2,3]
[1,2]
[1,3]
[1]
[2,3]
[2]
[3]
[]
In other words, getting a powerset is like getting all the combinations of keeping and throwing out elements from a set. For example, [2,3] is the original set with the number 1 excluded, [1,2] is the original set with 3 excluded, and so on.
To make a function that returns a powerset of some list, we’re going to rely on nondeterminism. We take the list [1,2,3] and then look at the first element, which is 1, and we ask ourselves, “Should we keep it or drop it?” Well, we would like to do both actually. So, we are going to filter a list, and we’ll use a predicate that nondeterministically both keeps and drops every element from the list. Here’s our powerset function:
powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs
Wait, that’s it? Yup. We choose to drop and keep every element, regardless of what that element is. We have a nondeterministic predicate, so the resulting list will also be a nondeterministic value and will thus be a list of lists. Let’s give this a go:
ghci> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
This takes a bit of thinking to wrap your head around. Just consider lists as nondeterministic values that don’t know what to be, so they decide to be everything at once, and the concept is a bit easier to grasp.
foldM
The monadic counterpart to foldl is foldM. If you remember your folds from Chapter 5, you know that foldl takes a binary function, a starting accumulator, and a list to fold up and then folds it from the left into a single value by using the binary function. foldM does the same thing, except it takes a binary function that produces a monadic value and folds the list up with that. Unsurprisingly, the resulting value is also monadic. The type of foldl is this:
foldl :: (a -> b -> a) -> a -> [b] -> a
Whereas foldM has the following type:
foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
The value that the binary function returns is monadic, so the result of the whole fold is monadic as well. Let’s sum a list of numbers with a fold:
ghci> foldl (\acc x -> acc + x) 0 [2,8,3,1]
14
The starting accumulator is 0, and then 2 is added to the accumulator, resulting in a new accumulator that has a value of 2. 8 is added to this accumulator, resulting in an accumulator of 10, and so on. When we reach the end, the final accumulator is the result.
Now, what if we wanted to sum a list of numbers but with the added condition that if any number in the list is greater than 9, the whole thing fails? It would make sense to use a binary function that checks if the current number is greater than 9. If it is, the function fails; if it isn’t, the function continues on its merry way. Because of this added possibility of failure, let’s make our binary function return a Maybe accumulator instead of a normal one. Here’s the binary function:
binSmalls :: Int -> Int -> Maybe Int
binSmalls acc x
| x > 9 = Nothing
| otherwise = Just (acc + x)
Because our binary function is now a monadic function, we can’t use it with the normal foldl; we must use foldM. Here goes:
ghci> foldM binSmalls 0 [2,8,3,1]
Just 14
ghci> foldM binSmalls 0 [2,11,3,1]
Nothing
Excellent! Because one number in the list was greater than 9, the whole thing resulted in a Nothing. Folding with a binary function that returns a Writer value is cool as well, because then you log whatever you want as your fold goes along its way.
Making a Safe RPN Calculator
When we were solving the problem of implementing an RPN calculator in Chapter 10, we noted that it worked fine as long as the input that it got made