-
Notifications
You must be signed in to change notification settings - Fork 410
Sized types allow a type which is both inductive and coinductive in an inconsistent way #1946
Copy link
Copy link
Open
Labels
coinductionCoinductive records, musical coinductionCoinductive records, musical coinductionfalseProof of the empty type which checks without known-unsafe flags (e.g. without --type-in-type)Proof of the empty type which checks without known-unsafe flags (e.g. without --type-in-type)infinity-less-than-infinityBugs relating to the ∞ < ∞ ruleBugs relating to the ∞ < ∞ rulesized typesSized types, termination checking with sized types, size inferenceSized types, termination checking with sized types, size inferencetype: bugIssues and pull requests about actual bugsIssues and pull requests about actual bugs
Milestone
Description
AIM XXIII, with Nisse and Andrea:
open import Common.Size
data SizeLt (i : Size) : Set where
size : (j : Size< i) → SizeLt i
-- Legal again in 2.5.1
getSize : ∀{i} → SizeLt i → Size
getSize (size j) = j
-- Structurally inductive (c), coinductive via sizes.
data U (i : Size) : Set where
c : ((s : SizeLt i) → U (getSize s)) → U i
data ⊥ : Set where
empty : U ∞ → ⊥
empty (c f) = empty (f (size ∞)) -- f x <= f < c f
-- If U is a data type this should not be possible:
inh : ∀ i → U i
inh i = c λ{ (size j) → inh j }
absurd : ⊥
absurd = empty (inh ∞)Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
coinductionCoinductive records, musical coinductionCoinductive records, musical coinductionfalseProof of the empty type which checks without known-unsafe flags (e.g. without --type-in-type)Proof of the empty type which checks without known-unsafe flags (e.g. without --type-in-type)infinity-less-than-infinityBugs relating to the ∞ < ∞ ruleBugs relating to the ∞ < ∞ rulesized typesSized types, termination checking with sized types, size inferenceSized types, termination checking with sized types, size inferencetype: bugIssues and pull requests about actual bugsIssues and pull requests about actual bugs