[Agda] Coinductive indices
Robert J. Simmons
rjsimmon at cs.cmu.edu
Tue Mar 15 21:14:34 CET 2011
I have a hopefully-simple question about coinduction. I have streams
of numbers under some constraint, they can be either labeled with
their cosize or not, and I want to show that I can take a stream and
turn it into a labeled stream.
open import Data.Nat renaming (ℕ to Nat)
open import Data.Conat renaming (Coℕ to Conat)
open import Coinduction
module Example where
data SmallStream (n : Nat) : Set where
nil : SmallStream n
cons : ∀{m}
(N : m ≤ n)
(S : ∞ (SmallStream n))
→ SmallStream n
data SmallStream' (n : Nat) : Conat → Set where
nil : SmallStream' n zero
cons : ∀{m size}
(N : m ≤ n)
(S : ∞ (SmallStream' n size))
→ SmallStream' n (suc (♯ size))
size : ∀{n} → SmallStream n → Conat
size nil = zero
size (cons N S) = suc (♯ size (♭ S))
mark : ∀{n} (S : SmallStream n) → SmallStream' n (size S)
mark nil = nil
mark (cons N S) = {!!}
I'm not clear on whether this is possible, partially due to the issues
raised in Conor's "generative thunk" thread from a while back.
I tried a number of avenues, including making the index of
SmallStream' a ∞ Conat instead of a Conat, which almost, but not
quite, worked. The real reason I'm interested in this is that the size
of a list or a colist is invariant under "weakening" (turning a
SmallStream 4 into a SmallStream 9). In the strictly-inductive
setting, my experience is that this sort of size is very useful as a
termination metric.
- Rob
--
Robert J. Simmons
simrob.com
gps.simrob.com
rjsimmon at cs.cmu.edu
robsimmons at gmail.com
Cell: 404-273-6890
More information about the Agda
mailing list