[Agda] Questions regarding non-constructor indexed datatypes
Shin-Cheng Mu
scm at iis.sinica.edu.tw
Sun Oct 12 19:19:30 CEST 2008
Hi,
Some more novice questions. :)
I was playing with the following implementation of a queue
using a pair of vectors:
data Queue {a : Set} : forall {n} -> Vec a n -> Set where
queue : forall {m n} ->
(l : Vec a m) -> (r : Vec a n) ->
Queue (l ++ reverse r)
The intention is that Queue xs is a queue whose content is
the vector xs, split into l and r such that xs = l ++ reverse r.
For this implementaiton of Queue, I am able to define, for
example, the following function enqueue:
enqueue : forall {a n} {xs : Vec a n} ->
(x : a) -> Queue xs -> Queue (x ∷ xs)
enqueue x (queue l r) = queue (x ∷ l) r
However, when I tried to define:
dequeue : forall {a k} {xs : Vec a (suc k)} ->
Queue xs -> (Queue (init xs) × a)
dequeue (queue {i} {j} l []) = ?
dequeue (queue l (r ∷ rs)) = ?
Agda highlighted the part "queue {i} {j} l []" and gave me
the error message:
m + n != suc k of type ℕ
when checking that the pattern queue {i} {j} l [] has type
Queue xs
Question 1: I guess the problem is that Agda tries to unify
i + j with suc k. In the case of enqueue, length l + length r
is unified with n, which poses no problem. It is not the
case with dequeue.
However, Agda refers to m and n, rather than i and j, so my
guess may be wrong. If so, what is going on here?
Question 2: What is the suggested approach to resolve the
problem above?
Question 3: The following function queue-eq (which proves
that if xs equals ys, then Queue xs can be cast to Queue ys)
passes the type checker:
queue-eq : forall {a n₁ n₂} {xs₁ : Vec a n₁} {xs₂ : Vec
a n₂} ->
xs₁ ≈ xs₂ -> Queue xs₁ -> Queue xs₂
queue-eq eq (queue l r) with length-equal eq
... | ≡-refl = ≅-subst Queue (to-≅ eq) (queue l r)
However, if I mention an implicit argument:
queue-eq {_}{n₁} eq (queue l r) with length-equal eq
... | ≡-refl = ≅-subst Queue (to-≅ eq) (queue l r)
The typecheck fails with a message similar to the one above:
m + n != n₁ of type ℕ
when checking that the pattern queue l r has type Queue xs₁
Why does simply mentioning the argument make a difference?
Thanks!
sincerely,
Shin
More information about the Agda
mailing list