Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell (n+1) in pattern matching

Tags:

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.

like image 766
Eugen Avatar asked Feb 06 '11 13:02

Eugen


People also ask

Where is pattern matching in Haskell?

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.

What is pattern matching in Haskell explain with example?

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.

Does Haskell have pattern matching?

(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.)


1 Answers

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.

like image 142
Thomas Avatar answered Sep 17 '22 01:09

Thomas