Archive for October, 2006

Kan Extensions for Functional Programmers

Saturday, October 28th, 2006 by Mauro Jaskelioff

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.

Busy day…

Friday, October 6th, 2006 by Peter

In an exceptionally busy fplunch:

  • Our visitor Daan Leijen gave a quick introduction to his research into using C# lambda expressions to allow programmers to introduce parallelism without the usual overheads. This served as an introduction to C# for most of the audience.
  • Liyang talked through his side project trying to introduce Conor’s idiom brackets using Template Haskell to do the transformations, he has some slides for more info — link coming soon
  • Conor then introduced his dissection work, showing how the a tail recursive fold for trees relies on a control structure which can be calculated for any fixed point of a polynomial (in fact any indexed container). This calculation is dissection and it generalises differentiation.