[Agda] Surprising type error in implementing decreasing lists
Alan Jeffrey
ajeffrey at bell-labs.com
Tue Jul 20 03:46:23 CEST 2010
Hi everyone,
I'm not sure what's going on here, am I missing something? Here's a
type which implements decreasing lists over a type (X : ℕ → Set):
data List<? (X : ℕ → Set) (n : ℕ) : Bool → Set where
[] : List<? X n true
_∷_ : {m : ℕ} → (x : X m) → (List<? X m true) → (List<? X n (m lt n))
List< : (ℕ → Set) → ℕ → Set
List< X n = List<? X n true
where lt is the obvious comparison function on ℕ. Now, if I try to
build some elements of type (List< A 3) where:
data A : ℕ → Set where
a1 : A 1
a2 : A 2
then as long as I explicitly give the type of [] I'm OK:
as : List< A 3
as = a2 ∷ a1 ∷ ([] {A})
but if I try to infer it:
as' : List< A 3
as' = a2 ∷ a1 ∷ []
then I get an error:
suc 0 != zero of type ℕ
when checking that the expression a1 has type A 0
Note, this is an error, not just some unsolved metavariables, which
surprises me.
Agda version 2.2.6 in case it makes a difference.
Any ideas anyone?
Alan.
-------------- next part --------------
open import Data.Nat
open import Data.Bool
module Weird where
infixr 5 _∷_
_lt_ : ℕ → ℕ → Bool
_ lt zero = false
zero lt suc _ = true
suc x lt suc y = x lt y
data List<? (X : ℕ → Set) (n : ℕ) : Bool → Set where
[] : List<? X n true
_∷_ : {m : ℕ} → (x : X m) → (List<? X m true) → (List<? X n (m lt n))
List< : (ℕ → Set) → ℕ → Set
List< X n = List<? X n true
data A : ℕ → Set where
a1 : A 1
a2 : A 2
as : List< A 3
as = a2 ∷ a1 ∷ ([] {A})
as' : List< A 3
as' = a2 ∷ a1 ∷ []
More information about the Agda
mailing list