How to define multiplication of Natural Numbers in Haskell commutatively?

Question

I was trying to define natural number multiplication in Haskell, and kept getting the error below (corresponds to the second natMult definition below).

Prelude> natMult (S (S Z)) (S (S Z))
*** Exception: <interactive>:(4,5)-(5,45): Non-exhaustive patterns in function natPlus

Here's my code:

data Nat = Z | S Nat deriving (Show)

natPlus :: Nat -> Nat -> Nat
natPlus Z a = a
natPlus (S a) (S b) = natPlus a (S (S b))

After a bit of tinkering, I realized this definition works fine, whereas the second one below is broken. The only difference is the order of the input parameters for natPlus.

-- works fine
natMult :: Nat -> Nat -> Nat
natMult Z a = Z
natMult (S a) b = natPlus (natMult a b) b

-- gives gives the error above
natMult :: Nat -> Nat -> Nat
natMult Z a = Z
natMult (S a) b = natPlus b (natMult a b)

Can anyone explain why this error arises?

---Edit--- The below definition is complete and solves the problem. Thanks for the suggestions

natPlus Z a = a
natPlus (S a) b = natPlus a (S b)

Your definition of `natPlus` looks a bit buggy - have you tried computing eg. `natPlus (S Z) Z`? — hnefatl, Apr 16 '18 at 20:38
I strongly recommend to turn on warnings, which would help you sport the issue immediately. — chi, Apr 16 '18 at 20:55

Willem Van Onsem · Answer 1 · 2018-04-16T20:55:00.637

In case of the Non-exhaustive patterns in function natPlus error, it is useful to compile with the -Wincomplete-patterns flag. If we compile the program with this flag we obtain:

$ ghci -Wincomplete-patterns 
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> data Nat = Z | S Nat deriving (Show)
Prelude> :{
Prelude| natPlus :: Nat -> Nat -> Nat
Prelude| natPlus Z a = a
Prelude| natPlus (S a) (S b) = natPlus a (S (S b))
Prelude| :}

<interactive>:4:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘natPlus’: Patterns not matched: (S _) Z

So the compiler warns us that for natPlus, the case natPlus (S _) Z is not covered. Since this is an exercise, I suggest that you define this case. So your code should look like:

natPlus :: Nat -> Nat -> Nat
natPlus Z a = a
natPlus (S a) (S b) = natPlus a (S (S b))
natPlus (S a) Z = -- ... your code here ...

Note that you can solve this by implementing a more generic pattern (for example natPlus a Z, You can try to define it in two clauses, for example natPlus Z a = -- ..., and natPlus (S a) b = -- ...

How to define multiplication of Natural Numbers in Haskell commutatively?

1 Answers1