I am trying to define a CoList without the delay constructors. I am running into a problem where I use a with expression but agda doesn't refine the type of a subcase.
module Failing where
open import Data.Unit
open import Data.Empty
open import Data.Maybe
open import Data.Nat
open import Data.Vec hiding (head ; tail ; map ; take)
record CoList (A : Set) : Set where
coinductive
field
head : Maybe A
tail : maybe (λ _ → ⊤) ⊥ head -> CoList A
open CoList
nil : ∀ {A} -> CoList A
head nil = nothing
tail nil ()
cons : ∀ {A} -> A -> CoList A -> CoList A
head (cons x xs) = just x
tail (cons x xs) tt = xs
take : ∀ {A} -> CoList A -> (n : ℕ) -> Maybe (Vec A n)
take l zero = just []
take l (suc n) with head l
... | nothing = nothing
... | just x = map (λ xs → x ∷ xs) (take (tail l {!!}) n)
The type of that hole is maybe (λ _ → ⊤) ⊥ (head l) but because of the with expression I would expect the type to be ⊤. I expect this because I withed on the head l and in that case head l = just x. If I try to fill the whole with tt agda mode gives me the following error:
⊤ !=< (maybe (λ _ → ⊤) ⊥ (head l)) of type Set
when checking that the expression tt has type
(maybe (λ _ → ⊤) ⊥ (head l))
I answered the question below, so now I am curious is there a better way to encode this list without the delay constructor?
You can think of with t as replacing t by whatever you match against, in the types of both function arguments and the goal. However, head l does not appear in your goal type when you perform the with — a goal whose type involves head l only appears later, once you have partially constructed the solution. This is the reason why your initial attempt doesn't work.
The inspect idiom, as demonstrated in your answer, is indeed the usual solution for this sort of problem.
As for encodings of coinductive types with 'more than one constructor', there are two (closely related) approaches that I'm aware of:
A mutual inductive/coinductive type:
data CoList′ (A : Set) : Set
record CoList (A : Set) : Set
data CoList′ A where
[] : CoList′ A
_∷_ : A → CoList A → CoList′ A
record CoList A where
coinductive
field
unfold : CoList′ A
open CoList
repeat : ∀ {A} → A → CoList A
repeat x .unfold = x ∷ repeat x
take : ∀ {A} → ℕ → CoList A → List A
take zero _ = []
take (suc n) xs with unfold xs
... | [] = []
... | x ∷ xs′ = x ∷ take n xs′
Taking the cofixpoint explicitly:
data CoList′ (A : Set) (CoList : Set) : Set where
[] : CoList′ A CoList
_∷_ : A → CoList → CoList′ A CoList
record CoList (A : Set) : Set where
coinductive
field
unfold : CoList′ A (CoList A)
open CoList
repeat : ∀ {A} → A → CoList A
repeat x .unfold = x ∷ repeat x
take : ∀ {A} → ℕ → CoList A → List A
take zero _ = []
take (suc n) xs with unfold xs
... | [] = []
... | x ∷ xs′ = x ∷ take n xs′