views:

229

answers:

5

I'm working my way through Graham Hutton's Haskell book, and in his recursion chapter, he often pattern-matches on "n+1", as in:

myReplicate1 0 _ = []
myReplicate1 (n+1) x = x : myReplicate1 n x

Why that and not the following, which (1) seems functionally identical and (2) more intuitive in terms of understanding what's happening with the recursion:

myReplicate2 0 _ = []
myReplicate2 n x = x : myReplicate2 (n-1) x

Is there something I'm missing here? Or is it just a matter of style?

+10  A: 

Those are n+k patterns (that should be avoided!) in the first function. Both functions do the same thing, except for the n+k one not matching negative numbers. The latter one, however, is recommended, and can be adopted if you want no negative numbers on purpose, because the n+k patterns are sheduled to be removed anyways.

So no, you're missing nothing, and it is indeed a matter of style, but I rarely see n+k patterns in the wild.

LukeN
In other words, it's a matter of style, and the first style is deprecated. :)
Nathan Sanders
Yup, just edited it in :)
LukeN
They're not the same actually. n+k patterns will not match negative numbers.
sepp2k
Whoops, didn't consider that! Thanks, sepp, I edited my answer!
LukeN
Very interesting - and I guess I WAS missing something (the n >= 0 bit). It's kind of strange magical behavior. I think it's funny that one of the arguments against removing it is that "some Haskell books use it" :)
rulfzid
+2  A: 

n+k patterns only match when n>=0. So in your myReplicate1 the n+1 pattern will match only positive numbers and a negative n will cause a nonexhaustive-pattern exception. In myReplicate2 a negative n would create an infinite list.

So in other words you can use n+k patterns when you don't want the pattern to match negative numbers, but using a guard instead will be clearer.

sepp2k
A: 
myReplicate n x = take n (repeat x)

Done and done. :D

Legatou
Yeah, that's real useful ...
Joren
+3  A: 

N+K patterns also have different strictness implications.

For example:

f (n+1) = Just n
g n = Just (n-1)

f is strict on its first argument, g is not. This is nothing special with n+k patterns but applies to all patterns.

phyrex1an
+5  A: 

I think the idea behind it is this: We can define a (slow) kind of natural number type like this:

data Natural = Zero | S Integer

So 0 == Zero, 1 == S Zero and so on.

When you do this, it becomes natural to use pattern matching like this:

myReplicate1 Zero _ = []
myReplicate1 (S n) x = x : myReplicate1 n x

I think (and it's just a guess) that the idea behind n+1 patterns is that it's like a fast version of what I just described. So n+1 is to be thought of like the pattern S n. So if you're thinking this way, n+1 patterns seem natural.

This also makes it clear why we have the side condition that n>=0. We can only represent n>=0 using the type Natural.