Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Haskell programming with nested types: a principled approach

Ghani, Neil and Johann, Patricia (2009) Haskell programming with nested types: a principled approach. Higher-Order and Symbolic Computation, 22 (2). pp. 155-189.

[img]
Preview
PDF
ghani_hosc09.pdf - Draft Version

Download (441kB) | Preview

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.

Item type: Article
ID code: 33724
Keywords: Software, Computer Science Applications
Subjects: UNSPECIFIED
Department: Faculty of Science > Computer and Information Sciences
Depositing user: Pure Administrator
Date Deposited: 18 Oct 2011 09:46
Last modified: 21 May 2015 13:43
URI: http://strathprints.strath.ac.uk/id/eprint/33724

Actions (login required)

View Item View Item