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.
We use pattern matching in Haskell to simplify our codes by identifying specific types of expression. We can also use if-else as an alternative to pattern matching. Pattern matching can also be seen as a kind of dynamic polymorphism where, based on the parameter list, different methods can be executed.
In a functional language, pattern matching involves checking an argument against different forms. A simple example involves recursively defined operations on lists. I will use OCaml to explain pattern matching since it's my functional language of choice, but the concepts are the same in F# and Haskell, AFAIK.
(Pattern matching in Haskell is different from that found in logic programming languages such as Prolog; in particular, it can be viewed as "one-way" matching, whereas Prolog allows "two-way" matching (via unification), along with implicit backtracking in its evaluation mechanism.)
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With