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?
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.
I think the idea behind it is this: We can define a type for the natural numbers (0, 1, ...) like this:
data Natural = Z -- zero
| S Natural -- one plus a number; the next number; the "successor"
0 = Z
, 1 = S Z
, and so on. This system is called Peano arithmetic, and is pretty much a standard in mathematics as a (starting point for a) definition of what a "number" actually is. You can go on to define Integer
s as pairs(-ish) of Natural
s, and so on.
When you do this, it becomes natural to use pattern matching like this:
myReplicate1 Z _ = []
myReplicate1 (S n) x = x : myReplicate1 n x
I think (and it's just a guess) that the idea behind n+1
patterns is a machine version of what I just described. So, n+1
is to be thought of like the pattern S n
. 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
.
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