Reference. Impredicative Encodings of Inductive and Coinductive Types
In impredicative type theory (System F, also known as λ2), it is possible to define inductive data types, such as natural numbers and lists. It is also possible to define coinductive data types such as streams. They work well in the sense that their (co)recursion principles obey the expected computation rules (the β-rules). Unfortunately, they do not yield a (co)induction principle [Herman Geuvers, 2001; Ivar Rummelhoff, 2004], because the necessary uniqueness principles are missing (the η-rules). Awodey, Frey, and Speight [Steve Awodey et al., 2018] used an extension of the Calculus of Constructions [Thierry Coquand and Gérard P. Huet, 1988] (λ C) with Σ-types, identity-types, and functional extensionality to define System F style inductive types with an induction principle, by encoding them as a well-chosen subtype, making them initial algebras. In this paper, we extend their results to coinductive data types, and we detail the example of the stream data type with the desired coinduction principle (also called bisimulation). To do that, we first define quotient types (with the desired η-rules) and we also need a stronger form of the definable existential types. We also show that we can use the original method by Awodey, Frey and Speight for general inductive types by defining W-types with an induction principle. The dual approach for streams can be extended to M-types, the generic notion of coinductive types, and the dual of W-types.
Cite
Cited by (1)
Impredicativity in Linear Dependent Type Theory speight-2026-impredicativity
We construct a realizability model of linear dependent type theory from a linear combinatory algebra. Our model motivates a number of additions to the type theory. In particular, we add a universe with two decoding operations: one takes codes to cartesian types and the other takes codes to linear types. The universe is impredicative in the sense that it is closed under both large cartesian dependent products and large linear dependent products. We also add a rule for injectivity of the modality turning linear terms into cartesian terms. With all of the additions, we are able to encode (linear) inductive types. As a case study, we consider the type of lists over a linear type, and demonstrate that our encoding has the relevant uniqueness principle. The construction of the realizability model is fully formalized in the proof assistant Rocq.
Cites 38 works (2 here)
With notes (2)
Internal Parametricity, without an Interval altenkirch-2024-internal
Parametricity is a property of the syntax of type theory implying, e.g., that there is only one function having the type of the polymorphic identity function. Parametricity is usually proven externally, and does not hold internally. Internalising it is difficult because once there is a term witnessing parametricity, it also has to be parametric itself and this results in the appearance of higher dimensional cubes. In previous theories with internal parametricity, either an explicit syntax for higher cubes is present or the theory is extended with a new sort for the interval. In this paper we present a type theory with internal parametricity which is a simple extension of Martin-Löf type theory: there are a few new type formers, term formers and equations. Geometry is not explicit in this syntax, but emergent: the new operations and equations only refer to objects up to dimension 3. We show that this theory is modelled by presheaves over the BCH cube category. Fibrancy conditions are not needed because we use span-based rather than relational parametricity. We define a gluing model for this theory implying that external parametricity and canonicity hold. The theory can be seen as a special case of a new kind of modal type theory, and it is the simplest setting in which the computational properties of higher observational type theory can be demonstrated.
External (36)
- hom-functor preserves limits (2024)
- The Rocq proof assistant (2024)
- Alternative impredicative encodings of inductive types (2023)
- Introduction to Homotopy Type Theory (2022)
- The lean 4 theorem prover and programming language (2021)
- Efficient lambda encodings for Mendler-style coinductive types in Cedille (2020)
- M-types and bisimulation (2020)
- Impredicative encodings of (higher) inductive types (2018)
- Generic derivation of induction for impredicative encodings in Cedille (2018)
- Strictly Positive Types in Homotopy Type Theory (2017)
- Impredicative encodings of inductive types in Homotopy Type Theory (2017)
- Non-wellfounded trees in homotopy type theory (2015)
- The Church-Scott representation of inductive and coinductive data (2014)
- Quotient Types in Type Theory (2014)
- Type Theory and Formal Proof: An Introduction (2014)
- Internalizing relational parametricity in the extensional calculus of constructions (2013)
- Inductive types in homotopy type theory (2012)
- An introduction to (co)algebra and (co)induction (2012)
- A brief overview of agda - A functional language with dependent types (2009)
- Non-well-founded trees in categories (2007)
- The Girard-Reynolds isomorphism (second edition) (2007)
- Containers: Constructing strictly positive types (2005)
- Polynat in PER models (2004)
- The Girard-Reynolds isomorphism (2003)
- Induction is not derivable in second order dependent type theory (2001)
- Structural induction and coinduction in a fibrational setting (1998)
- Proofs and types (1993)
- Inductive definitions in the system Coq - rules and properties (1993)
- Introduction to generalized type systems (1991)
- Inductively defined types in the Calculus of Constructions (1989)
- The Calculus of Constructions (1988)
- Inductively defined types (1988)
- Notes by Giovanni Sambin of a series of lectures in Padua, 1980 (1984)
- Towards a theory of type structure (1974)
- Une extension de l’interpretation de Gödel a l’analyse, et son application a l’elimination des coupures dans l’analyse et la theorie des types (1971)
- A formulation of the simple theory of types (1940)