[Agda] Codata and "with" matching
Shin-Cheng Mu
scm at iis.sinica.edu.tw
Tue Sep 2 18:55:02 CEST 2008
Hi,
This is about an anomaly that confused me when we were
experimenting with codata. The following code uses
the standard library.
---
module Stream where
open import Data.Nat
open import Data.Function
open import Data.Product
open import Relation.Binary.PropositionalEquality
{- Define stream as codata -}
codata Stream (A : Set) : Set where
_∷ˢ_ : A -> Stream A -> Stream A
{- head and tail -}
head : {A : Set} -> Stream A -> A
head (x ∷ˢ _) = x
tail : {A : Set} -> Stream A -> Stream A
tail (_ ∷ˢ xs) = xs
{- and unfold -}
unfoldˢ : {A B : Set} -> (B -> A × B) -> B -> Stream A
unfoldˢ f b with f b
... | (a , b') ~ a ∷ˢ unfoldˢ f b'
{- Bisimulation. Well, this is only bisimulation specialised
to streams. -}
codata _∼_ {A : Set} : Stream A -> Stream A -> Set where
bisim : {xs ys : Stream A} -> head xs ≡ head ys ->
tail xs ∼ tail ys -> xs ∼ ys
{- Now I would like to prove this unfold fusion rule -}
unfoldˢ-fusion : {A B C : Set} {f : B -> A × B} {h : C -> B} {g : C -
> A × C} ->
(forall x -> f (h x) ≡ map-× id h (g x)) ->
(forall x -> unfoldˢ f (h x) ∼ unfoldˢ g x)
unfoldˢ-fusion {f = f} {h = h} {g = g} fuse x ~ bisim {! !} {! !}
{- The two holes have (normalised) types:
?0 : (.Relation.Binary.Core._≡_ (head (unfoldˢ f (h x) | f (h
x)))
(head (unfoldˢ g x | g x)))
?1 : (tail (unfoldˢ f (h x) | f (h x)) ∼ tail (unfoldˢ g x | g
x))
which seem to hint at performing a "with" matching on
f (h x) or g x. Indeed it seems like the right thing to do
to expand the definitions before we can prove that
head (unfoldˢ f (h x)) equals head (unfoldˢ g x).
However, after performing a "with":
unfoldˢ-fusion {f = f} {h = h} {g = g} fuse x with f (h x)
... | (i , j) ~ bisim {! !} {! !}
The types of the holes do not change at all:
?0 : (.Relation.Binary.Core._≡_ (head (unfoldˢ f (h x) | f (h
x)))
(head (unfoldˢ g x | g x)))
?1 : (tail (unfoldˢ f (h x) | f (h x)) ∼ tail (unfoldˢ g x | g
x))
Why isn't "with" refining the types?
Thanks!
-}
More information about the Agda
mailing list