Generic Programming with Fixed Points for Mutually Recursive Datatypes Export

@inproceedings{citeulike:5733816, abstract = {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.}, address = {New York, NY, USA}, author = {Rodriguez Yakushev, Alexey and Holdermans, Stefan and L\"{o}h, Andres and Jeuring, Johan}, booktitle = {ICFP 2009}, citeulike-article-id = {5733816}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1596550.1596585}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1596550.1596585}, citeulike-linkout-2 = {http://people.cs.uu.nl/andres/Rec/MutualRec.pdf}, doi = {10.1145/1596550.1596585}, isbn = {978-1-60558-332-7}, keywords = {datatype-generic, fixed-point, generics, libraries, mutual-recursion, recursion, submit-gdiff, submit-incremental, zipper}, location = {Edinburgh, Scotland}, pages = {233--244}, posted-at = {2009-09-07 11:04:23}, priority = {0}, publisher = {ACM}, title = {Generic Programming with Fixed Points for Mutually Recursive Datatypes}, url = {http://dx.doi.org/10.1145/1596550.1596585}, year = {2009} }

TY - CONF ID - citeulike:5733816 L3 - citeulike-article-id:5733816 N2 - 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. CY - Edinburgh, Scotland SN - 978-1-60558-332-7 AD - New York, NY, USA EP - 244 TI - Generic Programming with Fixed Points for Mutually Recursive Datatypes PB - ACM T2 - ICFP 2009 SP - 233 KW - datatype-generic KW - fixed-point KW - generics KW - libraries KW - mutual-recursion KW - recursion KW - submit-gdiff KW - submit-incremental KW - zipper AU - Rodriguez Yakushev, Alexey AU - Holdermans, Stefan AU - Löh, Andres AU - Jeuring, Johan PY - 2009/// UR - http://dx.doi.org/10.1145/1596550.1596585 ER -