functional programming - 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 isn't these n + k patterns more allowed in Haskell 2010?

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.