[Agda] Two best practice questions
Edsko de Vries
edskodevries at gmail.com
Fri Dec 3 16:05:29 CET 2010
Hi,
I have two questions about best practice in Agda. The Agda tutorial
spends some time on the use of views; here is one example (from
another tutorial, on Epigram in fact):
data EqOrNot : Bool -> Bool -> Set where
same : {b : Bool} -> EqOrNot b b
diff : {b : Bool} -> EqOrNot b (not b)
eqOrNot : (a b : Bool) -> EqOrNot a b
eqOrNot true true = same
eqOrNot true false = diff
eqOrNot false true = diff
eqOrNot false false = same
Such a view allows us to define a function such as xor easily:
xor : (x y : Bool) -> Bool
xor x y with eqOrNot x y
xor x .x | same = false
xor x .(not x) | diff = true
However, why is it useful to define a custom datatype for such a view?
We could just as easily define:
eqOrNot' : (a b : Bool) -> a ≡ b ⊎ b ≡ not a
eqOrNot' true true = inj₁ refl
eqOrNot' true false = inj₂ refl
eqOrNot' false true = inj₂ refl
eqOrNot' false false = inj₁ refl
without using a special datatype, and we can still define xor just as
easily too:
xor' : (x y : Bool) -> Bool
xor' x y with eqOrNot' x y
xor' x .x | inj₁ refl = false
xor' x .(not x) | inj₂ refl = true
What is the advantage of the first approach over the second? (From a
pure readability perspective, to understand the type of eqOrNot we
need to know the constructors of EqOrNot, whereas we can understand
the type of eqOrNot' directly.)
In a related question (one that motivates the first, in fact),
consider the definition of a type that describes when an assertion is
satisfied:
_⊨_ : State -> Assn -> Set
σ ⊨ true = ⊤
σ ⊨ false = ⊥
σ ⊨ (! P) = (σ I ⊨ P) -> ⊥
-- and more clauses.. --
It seems that it would be more in line with Agda practice to define
this as a datatype instead:
data _⊨_ : State -> Assn -> Set where
sat-true : {σ : State} -> σ ⊨ true
-- no constructor for σ ⊨ false
sat-not : {σ : State} -> {P : Assn} -> ((σ ⊨ P) -> ⊥) -> σ ⊨ (! P)
-- and more constructors.. --
but this datatype definition is rejected, since there is a negative
occurrence in the definition for ! P -- even though this datatype is
clearly well-founded (defined by induction on the assertion). If there
are good reasons, above, to choose eqOrNot (using a special datatype)
over eqOrNot', then is a definition for ⊨ as a function instead of a
datatype going to get me into trouble later?
Thanks,
Edsko
More information about the Agda
mailing list