Haskell (n+1) in pattern matching

Question

I was doing the 99 Problems in Haskell when I encountered a solution to Problem 19 that I did not fully understand.

The task is to write a rotate function that works like this

*Main> rotate ['a','b','c','d','e','f','g','h'] 3
"defghabc"

*Main> rotate ['a','b','c','d','e','f','g','h'] (-2)
"ghabcdef"

One provided solution is

rotate [] _ = []
rotate l 0 = l
rotate (x:xs) (n+1) = rotate (xs ++ [x]) n
rotate l n = rotate l (length l + n)

I don't understand how the pattern matching can ever reach the fourth line. It seems to have to do with the (n+1) so that when n is negative the third line does not match and therefore the fourth is taken. If that is the case why does the notation (n+1) work that way resp. isn't that arbitrary or is that a convention (in mathematics?) that I'm not aware of?

Because the way I understand it is that rotate is called recursively in the third line with the argument n reduced by one. So I would think that

rotate [] _ = []
rotate l 0 = l
rotate (x:xs) n = rotate (xs ++ [x]) (n-1)
rotate l n = rotate l (length l + n)

is equivalent. However, it is not. This definition gives the following warning

Warning: Pattern match(es) are overlapped
         In the definition of `rotate': rotate l n = ...

whereas the former definition compiles just fine.

Thomas Thomas · Accepted Answer · 2011-02-06T13:38:33

It's a specific case of what is called "n+k patterns", which is generally disliked, and ~~will be~~ has been removed from the language. See here for more information.

Here is a good note on n+k patterns, which quotes the following from the Haskell 98 Report (emphasis mine):

Matching an n+k pattern (where n is a variable and k is a positive integer literal) against a value v succeeds if x >= k, resulting in the binding of n to x - k, and fails otherwise. Again, the functions >= and - are overloaded, depending on the type of the pattern. The match diverges if the comparison diverges.

The interpretation of the literal k is the same as in numeric literal patterns, except that only integer literals are allowed.

So the n+1 is only matched if n is at least 1, as you suspected. Your alternative code removes this restriction, resulting in overlapping pattern matches.

Haskell (n+1) in pattern matching

1 Answers