[Agda] proof by patterns

Sergei Meshveliani mechvel at botik.ru
Sat Feb 22 17:40:57 CET 2014


On Sat, 2014-02-22 at 15:04 +0100, Andreas Abel wrote:
> Why don't you simply match on argument "ft" of function "f" ?

Thank you.
Indeed, adding  "constructor ftCons"  and matching

  f a (ftCons (d ∷ d' ∷ []) all>1 a=d*d') ∣fs∣>1 =  composed-a
                                                    where ...
does work.
But in other examples, matched are some record members, not necessarily
field values.  
I do not know, I shall see the further practice.

------
Sergei




> On 21.02.2014 19:05, Sergei Meshveliani wrote:
> > 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
> >
> > _______________________________________________
> > Agda mailing list
> > Agda at lists.chalmers.se
> > https://lists.chalmers.se/mailman/listinfo/agda
> >
> 
> 




More information about the Agda mailing list