- 
author:
- Danel Ahmana
- James Chapmanb
- Tarmo Uustaluc
title: 'When is a Container a Comonad?'
---

[^1]

Introduction {#sec:intro}
============

Containers, as introduced by Abbott, Altenkirch and Ghani [@Abbott2005] are a neat representation for a wide class of parameterized datatypes (set functors) in terms of a set of shapes and a set of positions in each shape. They cover lists, colists, streams, various kinds of trees, etc. Containers can be used as a “syntax” for programming with these datatypes and reasoning about them, as can the strictly positive datatypes and polynomial functors of Dybjer [@dybjer1997], Moerdijk and Palmgren [@moerdijk.palmgren], Gambino and Hyland [@gambino.hyland:poly], and Kock [@kock:polyfuncandtrees]. The theory of this class of datatypes is elegant, as they are well-behaved in many respects.

This paper proceeds from the observation that datatypes often carry additional structure that containers alone do not account for. We introduce directed containers to capture the common situation in programming where every position in a data-structure determines another data-structure, informally, the sub-data-structure rooted by that position. Some natural examples of such data-structures are non-empty lists and node-labelled trees, and data-structures with a designated position or focus (zippers). In the former case, the sub-data-structure is a 