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 - Draft Version
Download (430Kb) | 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
    Subjects: UNSPECIFIED
    Department: Faculty of Science > Computer and Information Sciences
    Related URLs:
      Depositing user: Pure Administrator
      Date Deposited: 18 Oct 2011 10:46
      Last modified: 08 Dec 2013 19:45
      URI: http://strathprints.strath.ac.uk/id/eprint/33724

      Actions (login required)

      View Item

      Fulltext Downloads: