[Agda] a puzzle about pattern matching
Aaron Stump
aaron-stump at uiowa.edu
Mon Apr 13 23:46:51 CEST 2015
Dear Agda community,
For a while, I have wondered how to get Agda to understand that in a set
of equations defining some function, the patterns in earlier equations
must have failed to match, if we find ourselves in a later equation.
This could save a lot of repetitious equations. Below I have a small
example. It is completely self-contained (I have included the
definitions I am using from our Iowa Agda Library). The puzzle is, can
you prove lem in something closer to 3 equations, rather than the eight
given? Failing that, can you at least abstract out the eight equations
in some reasonably modular way? The problem is that action is defined
using default patterns, rather than explicit alternate patterns. The
proof of lem cannot just use default patterns, as partial evaluation of
applications of action requires that the patterns be explicit.
While this is obviously an artificial example, I find this issue comes
up rather frequently.
Cheers,
Aaron
module puzzle where
{----------- start standard definitions from IAL ---------------------}
data _≡_ {ℓ} {A : Set ℓ} (x : A) : A → Set ℓ where
refl : x ≡ x
{-# BUILTIN EQUALITY _≡_ #-}
{-# BUILTIN REFL refl #-}
import Agda.Primitive
open Agda.Primitive public
using (Level ; _⊔_ ; lsuc ; lzero)
level = Level
data ⊥ : Set where
⊥-elim : ⊥ → ∀ {P : Set} → P
⊥-elim ()
¬_ : ∀{ℓ}(x : Set ℓ) → Set ℓ
¬ x = x → ⊥
_≢_ : ∀ {ℓ}{A : Set ℓ} → A → A → Set ℓ
x ≢ y = ¬ (x ≡ y)
{----------- end standard definitions from IAL ---------------------}
data A : Set where
a : A
d : A → A → A → A
action : A → A
action (d a a a) = (d a a a)
action (d x y z) = a
action a = a
lem : ∀(x : A) → x ≢ d a a a → action x ≡ a
lem (d a a a) p = ⊥-elim (p refl)
lem (d a a (d z z₁ z₂)) p = refl
lem (d a (d y y₁ y₂) a) p = refl
lem (d a (d y y₁ y₂) (d z z₁ z₂)) p = refl
lem (d (d x x₁ x₂) a a) p = refl
lem (d (d x x₁ x₂) a (d z z₁ z₂)) p = refl
lem (d (d x x₁ x₂) (d y y₁ y₂) a) p = refl
lem (d (d x x₁ x₂) (d y y₁ y₂) (d z z₁ z₂)) p = refl
lem a p = refl
More information about the Agda
mailing list