[Agda] Re: merging identical proofs?

Andreas Abel abela at chalmers.se
Sat Feb 15 12:55:02 CET 2014


Kenichi Asai-san,

You need an indexed data type for this view.

data IdView {Γ} : ∀ τ (t : Term Γ τ) → Set where
   isId    : ∀{τ}   → IdView (TFun τ τ) (Lam (Var hd))
   isOther : ∀{τ t} → IdView τ t

idView : ∀ {τ Γ} (t : Term Γ τ) → IdView τ t
idView (Lam (Var hd)) = isId
idView _              = isOther

-- transformation: (λx.x) M -> M
f : ∀ {τ Γ} → Term Γ τ → Term Γ τ
f (Var x) = Var x
f (Lam t) = Lam (f t)
f (App t t₁) with idView t
f (App .(Lam (Var hd)) t₁) | isId    = f t₁
f (App t               t₁) | isOther = App (f t) (f t₁)

Best regards,
Andreas

On 15.02.2014 04:18, Kenichi Asai wrote:
>> If you want to only write these identical cases once, then there should
>> also be just a single corresponding case in `f`. You can do this with a
>> separate view:
>>
>>      zero-view : (t : Term) -> Maybe (t == Int 0)
>>      zero-view (Int zero) = just refl
>>      zero-view (Int (suc x)) = nothing
>>      zero-view (Add t t1) = nothing
>
> Thank you.  This is great.  Now, I gradually understand what the view
> is.  Let me ask one more question.  How can I define the view for a
> dependent case?  Concretely, suppose I want to replace all the
> occurrences of (\x.x) M in a term with M, where a term is defined
> typefully as usual:
>
> data Term (G : Ctx) : Type -> Set where
>    Var : forall {t} -> t in G -> Term G t
>    Lam : forall {t t'} -> Term (t :: G) t' -> Term G (TFun t t')
>    App : forall {t t'} -> Term G (TFun t t')  -> Term G t -> Term G t'
>
> When I define the translation:
>
> f : forall {t G} -> Term G t -> Term G t
> f (Var x) = Var x
> f (Lam t) = Lam (f t)
> f (App (Lam (Var hd)) t1) = f t1
> f (App t t1) = App (f t) (f t1)
>
> and want to change the last two cases using a view, I need to define a
> view something like:
>
> id-view : forall {t G} -> (T : Term G t) -> Maybe (T == Lam (Var hd))
>
> But it does not work, because the types of T and Lam (Var hd) do not
> agree.  What I want to define here would be:
>
> Given a term T for arbitrary G and t, if t has the form "TFun t' t'"
> for some t' and T == Lam (Var hd), then return just refl, otherwise
> nothing.
>
> Would this be possible?  Or should I do something else?
>
> Sincerely,
>
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>


-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Depeartment of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

andreas.abel at gu.se
http://www2.tcs.ifi.lmu.de/~abel/


More information about the Agda mailing list