[Agda] more unification using more complex with abstractions
rick
rick at rickmurphy.org
Tue Jul 31 20:00:29 CEST 2018
Given
data List (X : Set) : Set where
[] : List X
_,-_ : (x : X)(xs : List X) -> List X
data _==_ {X : Set} : X -> X -> Set where
refl : (x : X) -> x == x
_++_ : {A : Set} -> List A -> List A -> List A
[] ++ ys = ys
(x ,- xs) ++ ys = x ,- (xs ++ ys)
foldr : {A B : Set} -> (A -> B -> B) -> B -> List A -> B
foldr c n [] = n
foldr c n (x ,- xs) = c x (foldr c n xs)
unit : ∀{A} -> A -> List A
unit x = x ,- []
mult : {X : Set} -> List (List X) -> List X
mult = foldr _++_ []
Agda unifies the following:
um : ∀ {X} -> (xs : List X) -> mult (unit xs) == xs
um [] = refl []
um (x ,- xs) with mult (unit xs) | um xs
um (x ,- []) | [] | s = refl (x ,- [])
um (x ,- (x₁ ,- xs)) | [] | ()
um (x ,- .(x₁ ,- [])) | x₁ ,- []
| refl .(x₁ ,- []) = refl (x ,- (x₁ ,- []))
um (x ,- .(x₁ ,- (x₂ ,- r))) | x₁ ,- (x₂ ,- r)
| refl .(x₁ ,- (x₂ ,- r))
= refl (x ,- (x₁ ,- (x₂ ,- r)))
which proves propositional equality if you add a layer to the outside of
the list then flatten it.
The initial goal before pattern matching on with abstractions was (x ,-
r) == (x ,- xs).
However, given
listMap : {A B : Set} -> (A -> B) -> List A -> List B
listMap f xs = foldr (\ x r -> f x ,- r) [] xs
Agda does not unify the following :
mu : ∀ {X} -> (xss : List (List X))
-> listMap (mult (unit xss)) == xss
mu [] = refl []
mu (xs ,- xs₁) with listMap (mult (unit xs₁)) | mu xs₁
... | r | s = {! ((xs ++ []) ,- r) == (xs ,- xs₁) !}
which adds a layer to each list inside the list of lists, then flattens it.
I should qualify my statement and say does not unify within a few
pattern matching attempts before I stop to assess whether I can simplify.
I can prove the following lemma :
lem : ∀{X} -> (xs : List X)
-> (xs ++ []) == xs
lem [] = refl []
lem (x ,- xs) with (xs ++ []) | lem xs
lem (x ,- []) | [] | s = refl (x ,- [])
lem (x ,- (x₁ ,- xs)) | [] | ()
lem (x ,- []) | x₁ ,- [] | ()
lem (x ,- []) | x₁ ,- (x₂ ,- r) | ()
lem (x ,- (x₁ ,- xs)) | .x₁ ,- .xs | refl .(x₁ ,- xs) = refl (x ,- (x₁
,- xs))
which seems to allow for proving the concatenation on the first
component of the pair on the left hand side.
Can I use the lemma and if so how can I use it to cause Agda to unify mu?
Thanks in advance for your help! And for all the great work on Agda.
--
rick
More information about the Agda
mailing list