In
type theory,
containers are abstractions which permit various "collection types", such as
lists and
trees, to be represented in a uniform way. A (
unary) container is defined by a type of
shapes S and a type family of
positions P, indexed by S. The
extension of a container is a family of dependent pairs consisting of a shape (of type S) and a function from positions of that shape to the element type. Containers can be seen as
canonical forms for collection types.