CODEWITHSUNDEEP
pattern-matchingproofidrisdependent-type
vrom911
vrom911

Reputation: 694

Additional pattern matching on the second argument in `plus` for `Nat` type

I found out that plus function for Nats is implemented in this way

total plus : (n, m : Nat) -> Nat
plus Z right        = right
plus (S left) right = S (plus left right)

I wonder if there is particular reason not to pattern match on the second argument as well like here:

total plus : (n, m : Nat) -> Nat
plus Z right        = right
plus left Z         = left
plus (S left) right = S (plus left right)

As I see for the moment this implementation would make life simpler in many proofs and code. For example 

total plusZeroRightNeutral : (left : Nat) -> left + 0 = left
plusZeroRightNeutral Z     = Refl
plusZeroRightNeutral (S n) =
  let inductiveHypothesis = plusZeroRightNeutral n in
    rewrite inductiveHypothesis in Refl

would look like plusZeroLeftNeutral :

total plusZeroRightNeutral : (left : Nat) -> left + 0 = left
plusZeroRightNeutral left = Refl

In real life we don't even need to use plusZeroLeftNeutral theorem because Idris can do pattern matching automatically (as it already mentioned in the answer to this question: Concatenation of two vectors - why are lengths not treated as commutative? ).

So why not add extra cases to make life easier?

Upvotes: 3

Views: 104

Answers (1)

Anton Trunov
Anton Trunov

Reputation: 15414

Actually, plusZeroLeftNeutral cannot be proved with just Refl.

When you use Refl you are saying: "this holds by computation" (another name for this is definitional equality, or judgemental equality).

But how do we compute left + 0 (i.e. plus left Z for the Nat type)? Essentially, Idris processes function definitions clause by clause from top to bottom, and in our case it first looks at plus Z right clause. At this point Idris needs to decide if left is Z, but it cannot, because we have not destructed left. Idris cannot skip the first clause and go to plus left Z clause.

Now, with this alternative definition for plus one does not need induction for the proof of right neutrality of addition:

total plusZeroRightNeutral : (left : Nat) -> plus left 0 = left
plusZeroRightNeutral Z = Refl
plusZeroRightNeutral (S _) = Refl

But on the other hand, many proofs become long-winded because they now need more pattern-matching. Let's take the associativity of addition. Here is a possible proof for this fact for the original definition of plus:

total plusAssoc : (m,n,p : Nat) -> m + (n + p) = m + n + p
plusAssoc Z n p = Refl
plusAssoc (S m) n p = cong $ plusAssoc m n p

And here as the corresponding proof for the modified plus:

total plusAssoc : (m,n,p : Nat) -> m + (n + p) = m + n + p
plusAssoc Z n p = Refl
plusAssoc (S m) Z p = Refl
plusAssoc (S m) (S n) Z = Refl
plusAssoc (S m) (S n) (S p) = cong $ plusAssoc m (S n) (S p)

Here you are forced to destruct the second arguments of the occurrences of plus function simply because those block evaluation, but you need to move S constructors out of the way to be able to utilize your induction hypothesis.

Upvotes: 4

Related Questions