Home

Generic Programming With Fixed Points For Mutually Recursive Datatypes

Alexey

<!--
   * Set PREV_SKIN = customtitle
   * Set CUSTOMTOPICTITLE = Comparing Libraries for Generic Programming in Haskell
   * Set CUSTOMHEADTITLE = Comparing Libraries for Generic Programming in Haskell
   * Set WEBTITLE =
-->

_Alexey Rodriguez, Stefan Holdermans, Andres Löh, Johan Jeuring. Generic programming with fixed points for mutually recursive datatypes._

Many datatype-generic functions need access to the recursive positions in the
structure of the datatype, and therefore adopt a fixed point view on datatypes.
Examples include variants of fold that traverse the data following the
recursive structure, or the zipper data structure that enables navigation along
the recursive positions. However, Hindley-Milner-inspired type systems with
algebraic datatypes make it difficult to express fixed points for anything but
regular datatypes. Many real-life examples such as abstract syntax trees are
in fact systems of mutually recursive datatypes and therefore excluded. Using
Haskell's GADTs and type families, we describe a technique that allows a
fixed-point view for systems of mutually recursive datatypes. We demonstrate
that our approach is widely applicable by giving several examples of generic functions
for this view, most prominently the Zipper.

*Technical report:* [[http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html][url]]

-- Main.AlexeyRodriguez - 18 Jul 2008

Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
pdf	MutualRec-submitted.pdf	manage	181.8 K	18 Jul 2008 - 12:58	AlexeyRodriguez