[Agda] Problem with coinduction and positivity checker

Darin Morrison dmorri23 at cs.mcgill.ca
Tue Mar 17 16:54:49 CET 2009


Hi All,

I'm working on a constructive domain theory module where I need a
formalization of chains and ωchains but I'm having some problems with
the positivity checker.

Here is a snippet of the code I am using:

-- Chains

mutual
  data Chain : ℕ → Set where
    []    : Chain 0
    _∷_,_ : ∀ {n} (x : carrier) (xs : Chain n) (p : x ≼ xs) → Chain (suc n)

  _≼_ : ∀ {n} → carrier → Chain n → Set
  _ ≼ []           = ⊤
  x ≼ (x′ ∷ _ , _) = x ≤ x′

head : ∀ {n} → Chain (suc n) → carrier
head (x ∷ _ , _) = x

-- ωChains

mutual
  data ωChain : Set where
    _∷_,_ : ∀ (x : carrier) (xω : ∞ ωChain) (p : x ≼ xω) → ωChain

  head : ωChain → carrier
  head (x ∷ _ , _) = x

  _≼_ : carrier → ∞ ωChain → Set
  x ≼ xω = x ≤ head (♭ xω)

The above encoding of Chains works great.  However, Agda complains
that ωChain is not strictly positive because of (xω : ∞ ωChain).  Note
that I am using the Coinduction module described by Nils in a previous
post.

If I change the definition of ωChain to the following, the positivity
checker no longer complains:

mutual
  codata ωChain : Set where
    _∷_,_ : ∀ (x : carrier) (xω : ωChain) (p : x ≼ xω) → ωChain

  head : ωChain → carrier
  head (x ∷ _ , _) = x

  _≼_ : carrier → ωChain → Set
  x ≼ xω = x ≤ head xω

But this formulation is harder to work with for reasons discussed in
several recent posts on codata.

I'd rather not have to turn off the positivity checker.  Is there any
way to get around this?  Perhaps the positivity checker should be
modified not to complain in cases like this?

-- 
Darin


More information about the Agda mailing list