.. :: module language.telescopes where open import Agda.Builtin.Bool open import Agda.Builtin.Nat postulate List : Type → Type _++_ : {A : Type} → List A → List A → List A Vec : Type → Nat → Type IsTrue : Bool → Type Monoid : Type → Type NonZero : Nat → Type record _×_ (A B : Type) : Type where constructor _,_ field fst : A snd : B .. _telescopes: ********** Telescopes ********** A telescope is a non-empty sequence of variable bindings annotated by their types, with each variable surrounded by parentheses. For example, ``(x : Nat) (y : Bool) (z : Bool)`` is a telescope. Adjacent variables that have the same type can share a type annotation. For example, the same telescope can be written equivalently as ``(x : Nat) (y z : Bool)``. The type of each variable can depend on the previous variables in the telescope, for example ``(A : Type) (n : Nat) (v : Vec A n)``. .. note:: The terminology is due to de Bruijn :ref:`[1] `: "The word was inspired, of course, by the old-fashioned instrument consisting of segments that slide one into another." Each variable binding corresponds to a segment of the telescope, which can slide into (i.e. depend on) the previous ones. Telescopes appear in the following parts of the Agda syntax: * :ref:`Function types` * Declarations of :ref:`data types` and :ref:`record types` * Declarations of :ref:`parameterised modules ` :: postulate f : (A : Type) (n : Nat) (v : Vec A n) → Nat data D (A : Type) (n : Nat) (v : Vec A n) : Type where -- ... module M (A : Type) (n : Nat) (v : Vec A n) where -- ... In telescopes of data and record types as well as parameterised modules, it is allowed to omit the type of a variable binding. This is equivalent to giving the variable the type ``_`` (see :ref:`implicit arguments`). :: data D' A n (v : Vec A n) : Type where -- ... module M' A n (v : Vec A n) where -- ... In function types, the type of a variable binding can be omitted if the module telescope starts with ``forall`` or ``∀``. :: postulate f' : ∀ A n (v : Vec A n) → Nat When binding a variable of a :ref:`record type` (but not a data type), it is possible to deconstruct the bound variable by :ref:`pattern matching`: :: module N ((x , y) : Nat × Bool) where -- ... Variable bindings in a telescope can be :ref:`implicit ` or :ref:`instance ` arguments. For example: :: postulate mconcat : {A : Type} {{monoidA : Monoid A}} → List A → A Irrefutable Patterns in Binding Positions ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. :: module pattern-tele where open import Agda.Builtin.Sigma open import Agda.Builtin.Equality private variable A : Type B : A → Type Since Agda 2.6.1, irrefutable patterns can be used at every binding site in a telescope to take the bound value of record type apart. The type of the second projection out of a dependent pair will for instance naturally mention the value of the first projection. Its type can be defined directly using an irrefutable pattern as follows: :: proj₂ : ((a , _) : Σ A B) → B a And this second projection can be implemented with a lamba-abstraction using one of these irrefutable patterns taking the pair apart: :: proj₂ = λ (_ , b) → b Using an as-pattern makes it possible to name the argument and to take it apart at the same time. We can for instance prove that any pair is equal to the pairing of its first and second projections, a property commonly called eta-equality: :: eta : (p@(a , b) : Σ A B) → p ≡ (a , b) eta p = refl Since Agda 2.9.0, irrefutable patterns require that the deconstructed record has eta-equality. This is the case for ``Σ``, but e.g. not for ``coinductive`` records or records declared with ``no-eta-equality``. In the absence of eta-equality, irrefutable patterns trigger the warning :option:`ShouldBeEtaRecordPattern`. Let Bindings in Telescopes ~~~~~~~~~~~~~~~~~~~~~~~~~~ .. :: module let-bind-in-tele where Telescopes of function types and parameterised modules (but not of data and record types) can also contain :ref:`let bindings`. When used in this manner, the let-binding should be surrounded by parentheses and the ``in`` part of the syntax is omitted. For example: :: postulate g : (x : Nat) (let y = x + x) (v : Vec Nat y) → Nat Let-bound variables in a module telescope are available in the whole module. For example: :: module O (X : Type) (let LX = List X) (l : LX) where extend : LX → LX extend m = l ++ m In general, any valid let-binding can also be used in a telescope. For example, it is possible to pattern match on a record type with a let-binding: :: postulate h : (f : Nat → (Bool × Bool)) (let (x0 , y0) = f 0) (tx : IsTrue x0) → IsTrue y0 Another notable example is opening a :ref:`module` in a telescope: :: module M1 (X : Type) (let open M X) where This can also be written more compactly with just ``open`` (without the ``let``): :: module M2 (X : Type) (open M X) where .. _telescopes-refs: References ========== [1] N.G. de Bruijn. "`Telescopic mappings in typed lambda calculus. `_" Information and Computation, Volume 91, Issue 2, 1991.