In
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, an abstract branch of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, and in its applications to
logic and
theoretical computer science, a list object is an abstract definition of a
list, that is, a
finite ordered
sequence.
Formal definition
Let C be a
category with finite
products and a
terminal object 1.
A list object over an
object
Object may refer to:
General meanings
* Object (philosophy), a thing, being, or concept
** Object (abstract), an object which does not exist at any particular time or place
** Physical object, an identifiable collection of matter
* Goal, an ai ...
of C is:
# an object
,
# a
morphism
In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms a ...
: 1 →
, and
# a morphism
: ×
→
such that for any object of with maps : 1 → and : × → , there exists a unique :
→ such that the following diagram
commutes:
where〈id
, 〉denotes the arrow induced by the
universal property of the product when applied to id
(the identity on ) and . The notation * (
à la Kleene star) is sometimes used to denote lists over .
Equivalent definitions
In a category with a terminal object 1, binary
coproducts (denoted by +), and binary products (denoted by ×), a list object over can be defined as the
initial algebra of the
endofunctor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and ma ...
that acts on objects by ↦ 1 + ( × ) and on arrows by ↦
d1,〈id, 〉[ Philip Wadler]
Recursive types for free!
University of Glasgow, July 1998. Draft.
Examples
* In Set, the
category of sets, list objects over a set are simply finite lists with
elements
Element or elements may refer to:
Science
* Chemical element, a pure substance of one type of atom
* Heating element, a device that generates heat by electrical resistance
* Orbital elements, parameters required to identify a specific orbit of ...
drawn from . In this case,
picks out the empty list and
corresponds to appending an element to the head of the list.
* In the
calculus of inductive constructions or similar
type theories with inductive types (or heuristically, even
strongly typed
In computer programming, one of the many ways that programming languages are colloquially classified is whether the language's type system makes it strongly typed or weakly typed (loosely typed). However, there is no precise technical definition o ...
functional
Functional may refer to:
* Movements in architecture:
** Functionalism (architecture)
** Form follows function
* Functional group, combination of atoms within molecules
* Medical conditions without currently visible organic basis:
** Functional sy ...
languages such as
Haskell), lists are types defined by two constructors, nil and cons, which correspond to
and
, respectively. The recursion principle for lists guarantees they have the expected universal property.
Properties
Like all constructions defined by a
universal property, lists over an object are unique up to
canonical isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
.
The object
1 (lists over the terminal object) has the universal property of a
natural number object. In any category with lists, one can define the length of a list
to be the unique morphism :
→
1 which makes the following diagram commute:
References
*
See also
*
Natural number object
*
F-algebra
In mathematics, specifically in category theory, ''F''-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algeb ...
*
Initial algebra
{{Category theory
Objects (category theory)
Topos theory