Haskell: Non-exhaustive pattern - Checking if list is ascending

Question

I have no idea why my function doesn't work. I have gone through all the posts about non-exhaustive functions but my functions fulfills all possible options as far as I can see.

ascending :: [Int] -> Bool
ascending []                = error "Empty list given"
ascending [x]               = True
ascending [x,y]     | y>=x  = True
                    | x<y   = False
ascending (x:y:xs)  | y>=x  = (ascending (y:xs))
                    | x<y   = False

Result:

*Main> ascending []
*** Exception: Empty list given
*Main> ascending [1]
True
*Main> ascending [1, 2]
True
*Main> ascending [2, 1]
*** Exception: test01.hs:(51,1)-(56,55): Non-exhaustive patterns in function ascending

It works for one pair, but not if the pair is not ascending. When I follow my code it should be just returning False.

Recency

Look at the comparisons carefully. Which branch should it go down when it gets called with [2, 1]? – Falster

@David I would have thought it would go down ascending [x, y] with x = 2 and y = 1..... And then it clicked.... I feel like an idiot. Well now I know that 'non-exhaustive' also includes guards. Thanks! – Recency

GHC should warn about this statically, if you enable warnings. Very roughly, if the last guard is not otherwise or True, then the case branch is considered not exhaustive, and unless there's another branch below catching the potentially non-matched terms, it will trigger the warning. IMO, I'd like this to be a compile-time error (as in Agda, etc.) so to force the programmer to write all the cases, even if some of them are simply undefined. – Overton

Answer 1

Have a closer look at the guards for your [x,y] pattern:

ascending [x,y] | y>=x = True
                | x<y  = False

When applied to [2,1], the first guard is checked and evaluates to False (because 2 >= 1); then, the second guard is checked, but it also evaluates to False (because 1 < 2). Therefore, the next pattern is used (because [2,1] also matched (x:y:ys)), but exactly the same thing happens. Because this was the last pattern, GHC rightfully screams at you.

The inequalities in your guards are not complementary. Your third pattern should read

ascending [x,y] | x <= y = True
                | x >  y = False

or, to leave less room for error,

ascending [x,y] | x <= y    = True
                | otherwise = False

However, there is still much room for improvement. In particular:

• The third pattern overlaps with the fourth one.
• Because your function returns a Bool, using guards only to explicitly return a Boolean value is redundant.
• Because, by convention (see dfeuer's comment), the empty list is considered to be ascending, you don't need to throw an error upon encountering it (unless you're following your own whimsical convention).

Taking all this into account, you could have simply written

ascending :: [Int] -> Bool
ascending (x:y:xs) = x <= y && ascending (y:xs)
ascending _        = True

Finally, you can condense the code some more with a combination of and and zipWith:

ascending :: [Int] -> Bool
ascending xs = and $ zipWith (<=) xs (tail xs)

Micmac

A very comprehensive answer. Thank you. – Recency

@deadfire19, finally finally, an empty list is vacuously ascending, so there's no need to make that case an error. ascending [] = True will do just fine. Or you can move the last case to the beginning and then make a second case ascending _ = True. – Actinoid