Research papers/Functional pearls

Functional pearls are elegant, instructive examples of functional programming, traditionally appearing in The Journal of Functional Programming, and at ICFP and affiliated workshops.

How to Write a Functional Pearl: Richard Bird. ICFP 2006.

Fifteen years of functional pearls: Richard Bird. ICFP 2006.

Strachey's functional pearl, forty years on: Mike Spivey, 2006.

Online

Functional pearls online:

Enumerating the rationals: Jeremy Gibbons, David Lester and Richard Bird. 2006.

Probabilistic functional programming in Haskell: Martin Erwig and Steve Kollmansberger. 2006.

Marble mingling: Sharon Curtis. 2006.

Strong Types for Relational Databases: Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)

Backtracking, interleaving, and terminating monad transformers: Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005.

Scrap your Nameplate: James Cheney. 2005.

Enumerating the strings of regular languages: M. Douglas McIlroy. 2004.

Implicit configurations--or, type classes reflect the values of types: Oleg Kiselyov, Chung-chieh Shan. 2004. (also here)

Global variables in Haskell: John Hughes. 2004. (JFP)

I am not a number -- I am a free variable: Conor McBride, James McKinna. 2004.

Inverting the Burrows Wheeler transform: Richard Bird and Shin-Cheng Mu. 2004.

Parsing permutation phrases: Arthur Baars, Andres L�h and S. Doaitse Swierstra. 2004.

Concurrent distinct choices: Sergio Antoy and Michael Hanus. 2004.

Functional chart parsing of context-free grammars: Peter Ljungl�f. 2004.

Type-Safe Cast: Stephanie Weirich. 2004.

Pickler Combinators: Andrew J. Kennedy. 2004.

Parallel Parsing Processes: Koen Claessen. 2004.

Producing all ideals of a forest, functionally: Jean-Christophe Filli�tre and Fran�ois Pottier. 2003.

Trouble shared is trouble halved: Richard Bird, Ralf Hinze. 2003

A fresh look at binary search trees: Ralf Hinze. 2002.

The countdown problem: Graham Hutton. 2002.

Packrat parsing: simple, powerful, lazy, linear time, functional pearl: Bryan Ford. 2002.

Unfolding pointer algorithms: Richard Bird. 2001.

Maximum marking problems: Richard Bird. 2001.

Weaving a web: Ralf Hinze and Johan Jeuring. 2001.

Normalization by evaluation with typed abstract syntax: Olivier Danvy, Morten Rhiger and Kristoffer H. Rose. 2001.

Do we need dependent types?: Daniel Fridlender and Mia Indrika. 2001.

Perfect trees and bit-reversal permutations: Ralf Hinze. 2000.

Combinators for breadth-first search: Michael Spivey. 2000

Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design: Chris Okasaki. 2000.

Deriving Backtracking Monad Transformers: Ralf Hinze. 2000.

Recursive subtyping revealed: Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. 2000.

Composing contracts: an adventure in financial engineering: Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.

A poor man's concurrency monad: Koen Claessen. 1999.

Power series, power serious: M. Douglas McIlroy. 1999.

Proof-directed debugging: Robert Harper. 1999. (see also Proof-directed debugging: revisited for a first-order version).

Monadic parsing in Haskell: Graham Hutton and Erik Meijer . 1998.

Polytypic unification: Patrik Jansson and Johan Jeuring. 1998.

Diets for fat sets: Martin Erwig. 1998.

Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?: Chris Okasaki. 1998.

Lazy wheel sieves and spirals of primes: Colin Runciman. 1997.

The Third Homomorphism Theorem: Jeremy Gibbons. 1996.

Back to Basics: Deriving Representation Changers Functionally.: Graham Hutton, Erik Meijer. 1996.

Drawing Trees: Drawing Trees. 1996.

Deriving Tidy Drawings of Trees: Jeremy Gibbons. 1996. (See also the research report).

Offline

These appear not available online, unfortunately. If you know where they live, please link, and move into the 'online' section!

Finding celebrities: A lesson in functional programming: Richard Bird and Sharon Curtis. 2006.

A program to solve Sudoku: Richard Bird. 2006.

On tiling a chessboard: Richard Bird. 2004.

Linear lambda calculus and PTIME-completeness: Harry G. Mairson. 2004

Functional satisfaction: Luc Maranget. 2004.

Derivation of a logarithmic time carry lookahead addition circuit: John T. O'Donnell and Gudula R�nger. 2004.

Composing fractals: Mark P. Jones. 2004.

Calculating the Sieve of Eratosthenes: Lambert Meertens. 2004. (slides)

Formatting: a class act: Ralf Hinze . 2003.

Red-black trees with types: Stefan Kahrs. 2001. (also)

Explaining binomial heaps: Ralf Hinze. 1999.

A pointless derivation of radix sort: Jeremy Gibbons. 1999.

Red-black trees in a functional setting: Chris Okasaki. 1999.

Meertens number: Richard Bird. 1998.

On merging and selection: Richard Bird. 1997. (See also More on Merging and Selection).

On building trees with minimum height: Richard Bird. 1997.

The Zipper: G�rard Huet. 1997. (See also The Haskell Wikibook).

Three algorithms on Braun trees: Chris Okasaki. 1997.

On generating unique names: L Augustsson, M Rittri, D Synek. 1994.

Efficient Sets - A Balancing Act: Stephen Adams. 1993.

The Last Tail.: Richard Bird. 1993.

A Symmetric Set of Efficient List Operations.: Rob R. Hoogerwoord, 1992.

Two Greedy Algorithms: Richard Bird, 1992.

On Removing Duplicates: Richard Bird. 1991.