[Agda] proof by patterns
Sergei Meshveliani
mechvel at botik.ru
Fri Feb 21 19:05:48 CET 2014
People,
I have the following difficulties with a proof by patterns:
-------------------------------------------------------------------------
open import Function using (case_of_)
open import Relation.Binary.PropositionalEquality as PE using (_≡_; _≢_)
open import Data.Empty using (⊥-elim; ⊥)
open import Data.Nat using (ℕ; _*_; _<_; _>_; _≯_)
open import Data.Product using (_×_; _,_; ∃₂)
open import Data.List using (List; []; _∷_; length; foldr)
open import Data.List.All as All using ()
postulate anything : ∀ {a} {A : Set a} → A
-- This is about decomposition of a natural into a product.
IsComposed : ℕ → Set
IsComposed n = ∃₂ \ l m → l > 1 × m > 1 × n ≡ l * m
Π : List ℕ → ℕ
Π = foldr _*_ 1
record Ft (a : ℕ) : Set where -- something like a factorization
field -- structure (contrived)
factors : List ℕ
all>1 : All.All (_>_ 1) factors
eq : a ≡ Π factors
f : (a : ℕ) → (ft : Ft a) → (length (Ft.factors ft)) > 1 → IsComposed a
--
-- decompose a to d * d' by using the factorization structure
f a ft ∣fs∣>1 with Ft.factors ft
... | d ∷ d' ∷ [] = composed-a
where
fs = Ft.factors ft
e0 : a ≡ Π fs
e0 = Ft.eq ft
e : a ≡ Π (d ∷ d' ∷ [])
e = Ft.eq ft
-- postulate
composed-a : isComposed a
...
... | _ = ...
--------------------------------------------------------------
I hoped for the field eq to provide a proof for
a ≡ Π (d ∷ d' ∷ [])
in the first branch.
And then, one could derive the decomposition a ≡ d * d'.
The line "e : ..." starts to check this approach.
1.
But "e = ..." is not type-checked. As it often occurs, Agda does not
see that eq holds for d ∷ d' ∷ [], despite that this pattern is a
special case of Ft.factors.
Such is a strange nature of patters in Agda. It is difficult to get used
to it.
Can this `with' or `case' be fixed in this example?
2.
After I have given up with case/with, I find that this approach works:
------------------------------------------------------------------
f a ft ∣fs∣>1 = g (Ft.factors ft) (Ft.all>1 ft) (Ft.eq ft)
-- extract all the fields and put their values to one signature
-- simultaneously
where
g : (fs : List ℕ) → All.All (_>_ 1) fs → a ≡ Π fs → IsComposed a
g (d ∷ d' ∷ []) all>1 a=product = composed-a
where
e : a ≡ d * (d' * 1)
e = a=product -- this works
composed-a : IsComposed a
...
------------------------------------------------------------------
But for a record of 10 dependent fields, the signature for g may
occur too large and complex.
What is a regular way out?
Is it trying to refine the approach of `g' in each particular case?
Thank you in advance for explanation,
------
Sergei
More information about the Agda
mailing list