Haskell Programming with Nested Types: A Principled Approach

ASU Author/Contributor (non-ASU co-authors, if there are any, appear on document)
Patricia Johann Ph.D, Professor (Creator)
Institution
Appalachian State University (ASU )
Web Site: https://library.appstate.edu/

Abstract: Initial algebra semantics is one of the cornerstones of the theory of modern functional programming languages. For each inductive data type, it provides a Church encoding for that type, a build combinator which constructs data of that type, a fold combinator which encapsulates structured recursion over data of that type, and a fold/build rule which optimises modular programs by eliminating from them data constructed using the build combinator, and immediately consumed using the fold combinator, for that type. It has long been thought that initial algebra semantics is not expressive enough to provide a similar foundation for programming with nested types in Haskell. Specifically, the standard folds derived from initial algebra semantics have been considered too weak to capture commonly occurring patterns of recursion over data of nested types in Haskell, and no build combinators or fold/build rules have until now been defined for nested types. This paper shows that standard folds are, in fact, sufficiently expressive for programming with nested types in Haskell. It also defines build combinators and fold/build fusion rules for nested types. It thus shows how initial algebra semantics provides a principled, expressive, and elegant foundation for programming with nested types in Haskell.

Additional Information

Publication
Johann, Patricia; Ghani, Neil. (2009) Haskell Programming with Nested Types: A Principled Approach. Higher-Order and Symbolic Computation, vol. 22, no. 2 (June 2009), pp. 155 - 189. ISSN: 1573-0557
Language: English
Date: 2009
Keywords
nested type, initial algebra semantics, principled Approach, build combinator, standard fold

Email this document to