Why does my Haskell do-notation break when I try to desugar it?

Question

I have the following code from Problem 26 of the 99 Haskell problems:

combinations :: Int -> [a] -> [[a]]
combinations 0 _  = return []
combinations n xs = do y:xs' <- tails xs
                       ys <- combinations (n-1) xs'
                       return (y:ys)

The above code works as expected. Below is my main function and the printed results:

main = print $ combinations 2 "abcd"
-- Prints: ["ab","ac","ad","bc","bd","cd"]

As a learning exercise I tried to "desugar" the do-notation like so:

combinations :: Int -> [a] -> [[a]]
combinations 0 _  = return []
combinations n xs = tails xs >>= \(y:xs') ->
                    do
                        ys <- combinations (n-1) xs'
                        return (y:ys)

This compiles, but gives the following error at runtime:

PatternMatchFail: /home/.../test.hs:(46,34)-(49,37): Non-exhaustive patterns in lambda

What is going on here? How can I replace the do-notation with >>= and >>?

Answer 1

From the Haskell Wikibook:

... the snippet with lambdas was "broadly equivalent" to the do block. It is not an exact translation because the do notation adds special handling of pattern match failures.

Consider this example:

f xs = do
       (x:_) <- Just xs
       return x  

g xs = Just xs >>=
       \(x:_) -> return x

For any non-empty list, these functions are identical. But f [] returns Nothing, and g [] returns an error much like the one you're getting.

This is because the do notation handles failure differently. The Monad typeclass has a fail function. You're using the list monad, which fails by returning an empty list. The Maybe monad implement it by returning Nothing. Either way, the pattern match failure inside the do notation is handled with this function, hence the difference.

So the correct way to translate it would be:

g xs = Just xs >>= 
       \xs' -> case xs' of
                 (x:_) -> return x
                 []    -> fail "some error"