13

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 >>?

Community
  • 1
  • 1
Buttons840
  • 9,239
  • 15
  • 58
  • 85

1 Answers1

15

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"
Benesh
  • 3,398
  • 1
  • 18
  • 38
  • As a beginner, I now feel all these sayings of "it's just syntax sugar" are harmful. I know it's technically true, but I've had it presented to me several times that do-notation is a mere convenience to limit the number of >>= and >> I have to write. – Buttons840 Mar 28 '14 at 16:58
  • 3
    @Buttons840 It _is_ a mere convenience, just a bit more of one than you thought. – Alexey Romanov Mar 28 '14 at 17:40
  • 2
    @Buttons840 It _is_ syntactic sugar. It doesn't do any magic you couldn't do without the do notation. – Cubic Mar 28 '14 at 18:35
  • Personally, I believe that "you can deal without it" is a bad reason to avoid something. Everybody knows that decimal integers are converted to binary in the compilation, yet avoiding decimals is a stupid idea. – Benesh Mar 28 '14 at 19:03
  • @Benesh - I agree it is a bad reason and never intended to suggest otherwise. I meant that the do-notation explanations and "tutorials" I have encountered did not mention the error handling behavior clearly enough that I caught-on to it. All the explanations focused on do-notation's relation with >> and >>=, with little mention of error handling, but it seems this error handling behavior is equally important yet rarely mentioned. – Buttons840 Mar 28 '14 at 19:42
  • 1
    @Buttons840 not "error handling behavior" in general, but behavior on pattern-mismatch, in particular. Just clarifying. :) – Will Ness Apr 07 '14 at 11:08