[Agda] Negative coinductive sized types

Florian Engel florian.engel at student.uni-tuebingen.de
Tue Nov 3 21:27:44 CET 2020


Hi all,

I'm trying to implement the ham function from [1]

This is how far I've get so far

  record Stream (i : Size) (A : Set) : Set where
    coinductive
    field
      hd : A
      tl : ∀ {j : Size< i} → Stream j A
  open Stream

  cons : {i : Size} {j : Size< i} {A : Set} → A -> Stream i A → Stream j A
  hd (cons x _)  = x
  tl (cons _ xs) = xs

  leq : {C : Set} → ℕ ∞ → ℕ ∞ → C → C → C
  leq zero    _       t _ = t
  leq (suc x) zero    _ f = f
  leq (suc x) (suc y) t f = leq x y t f

  merge : {i : Size} → Stream i (ℕ ∞) → Stream i (ℕ ∞) → Stream i (ℕ ∞)
  hd (merge xs ys) = min (hd xs) (hd ys)
  tl (merge xs ys) = leq (hd xs) (hd ys)
                         (cons (hd ys) (merge (tl xs) (tl ys)))
                         (cons (hd xs) (merge (tl xs) (tl ys)))

agda cannot solve the size constraints for merge in the tl case because
the output depth of cons is smaller than the input.  I don't understand
why i can't give cons the type

  cons : {i : Size} {j : Size< i} {A : Set} → A -> Stream j A → Stream i A

Shouldn't the minimal depth of the output be larger than the input?

Best regards
Florian

[1] https://www.researchgate.net/publication/220485445_MiniAgda_Integrating_Sized_and_Dependent_Types
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20201103/bcaceb44/attachment.sig>


More information about the Agda mailing list