Nottingham FP Lab Blog

Kan Extensions for Functional Programmers

by Mauro Jaskelioff on October 28, 2006.
Tagged as: Lunches.

Neil talked about his forthcoming book

Here is the summary:

Inductive types have a well understood theory in terms of initial algebra semantics on a category of types. When it comes to advanced types, like nested datatypes and GADTs, the key idea seems to be that types should be indexed but there is disagreement about what these indexes are.

In the functional world, the Haskell community has swallowed the “practical” benefits of GADTs where indexes are elements of $\star$ , eg:

$Lam\colon \star \rightarrow \star$

The theoretical advantages of using the dependently typed approach, where $$Lam\colon \mathbb{N} \rightarrow \star$ , are seen as just “academic”. The semantics here is in terms of slice categories where the key constructions are reindexing, dependent sum & product.

Their equivalents in the functional world are functor composition and left and right Kan extensions. So all the practical Haskellers are buying into MacLane’s chapter X.