What are "n+k patterns" and why are they banned from Haskell 2010?

Question

When reading Wikipedia's entry on Haskell 2010 I stumbled across this:

-- using only prefix notation and n+k-patterns (no longer allowed in Haskell 2010)
factorial 0 = 1
factorial (n+1) = (*) (n+1) (factorial n)

What do they mean by "n+k patterns"? I guess it's the second line, but I don't get what might be wrong with it. Could anyone explain what is the issue there? Why aren't these n + k patterns allowed any more in Haskell 2010?

Anamorphic

for a hint of perhaps the why of n+k patterns check out this excellent blog post: blog.sigfpe.com/2007/07/data-and-codata.html – Esmaria

For people who still want to use the n+k-pattern (I'm looking at you, Erik Meijer), there is -XNPlusKPatterns or {-# LANGUAGE NPlusKPatterns #-} – Eremite

Answer 1

What are n+k patterns? Take a gander at this:

$ ghci
GHCi, version 6.12.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> let f 0 = 0 ; f (n+5) = n
Prelude> :t f
f :: (Integral t) => t -> t
Prelude> f 0
0
Prelude> f 1
*** Exception: <interactive>:1:4-24: Non-exhaustive patterns in function f

Prelude> f 2
*** Exception: <interactive>:1:4-24: Non-exhaustive patterns in function f

Prelude> f 3
*** Exception: <interactive>:1:4-24: Non-exhaustive patterns in function f

Prelude> f 4
*** Exception: <interactive>:1:4-24: Non-exhaustive patterns in function f

Prelude> f 5
0
Prelude> f 6
1

They're basically an extremely special case on pattern matching which only work on numbers and which do ... well, let's just be polite and call it "unexpected things" to those numbers.

Here I have a function f which has two clauses. The first clause matches 0 and only 0. The second clause matches any value of type Integral whose value is 5 or greater. The bound name (n, in this case) has a value equal to the number you passed in minus 5. As to why they've been removed from Haskell 2010, I hope you can see the reason now with just a bit of thinking. (Hint: consider the "principle of least surprise" and how it may or may not apply here.)

---

Edited to add:

A natural question to arise now that these constructs are forbidden is "what do you use to replace them?"

$ ghci
GHCi, version 6.12.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> let f 0 = 0 ; f n | n >= 5 = n - 5
Prelude> :t f
f :: (Num t, Ord t) => t -> t
Prelude> f 0
0
Prelude> f 1
*** Exception: <interactive>:1:4-33: Non-exhaustive patterns in function f

Prelude> f 2
*** Exception: <interactive>:1:4-33: Non-exhaustive patterns in function f

Prelude> f 3
*** Exception: <interactive>:1:4-33: Non-exhaustive patterns in function f

Prelude> f 4
*** Exception: <interactive>:1:4-33: Non-exhaustive patterns in function f

Prelude> f 5
0
Prelude> f 6
1

You'll notice from the type statements that these are not precisely equal, but the use of a guard is "equal enough". The use of the n-5 in the expression could get tedious and error-prone in any code that uses it in more than one place. The answer would be to use a where clause along the lines of this:

Prelude> let f 0 = 0 ; f n | n >= 5 = n' where n' = n - 5
Prelude> :t f
f :: (Num t, Ord t) => t -> t
Prelude> f 0
0
Prelude> f 5
0
Prelude> f 6
1

The where clause lets you use the calculated expression in multiple places without risk of mistyping. There is still the annoyance of having to edit the border value (5 in this case) in two separate locations in the function definition, but personally I feel this is a small price to pay for the increase in cognitive comprehension.

---

Further edited to add:

If you prefer let expressions over where clauses, this is an alternative:

Prelude> let f 0 = 0 ; f n | n >= 5 = let n' = n - 5 in n'
Prelude> :t f
f :: (Num t, Ord t) => t -> t
Prelude> f 0
0
Prelude> f 5
0

And that's it. I'm really done now.

Apologetics

Great answer! I'm pretty new to Haskell so my next question would be: why does the type checker allow that pattern and doesn't issue at least a warning? In this case it must know that that code is missing some cases. – Cist

You can fix the type signature pretty easily: let f 0 = 0 ; f n | toInteger n >= 5 = n' where n' = n - 5. – Homeric

Why does the pattern match fail for 0 < n < 5? I would expect n to match negative numbers in those cases. – Elevate

You can put lets in pattern guards, too, so you can also write let f 0 = 0; f n | let n' = n - 5, n' >= 0 = n' – Titre

Answer 2

The link provided by trinithis is correct; n+k patterns are no longer included in the Haskell spec.

For more background on n+k patterns in general, scroll about 3/5ths of the way down this page on pattern matching, or check out this short post.

Circumcise