Research papers/Functional pearls

Functional pearls are elegant, instructive examples of functional programming. They are supposed to be fun, and they teach important programming techniques and fundamental design principles. They traditionally appear in The Journal of Functional Programming, and at ICFP and affiliated workshops.

The history of functional pearls is covered by:

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.

On Barron and Strachey's Cartesian Product Function

Olivier Danvy and Michael Spivey, July 2007

There have been some 64 functional pearls in JFP, and some others at ICFP and the Haskell Workshop. There is also a collection of them in The Fun of Programming.

The pearls tend to concentrate on:

• Examples of program calculation and proof
• Neat presentations of new or old data structures
• Interesting applications and techniques

Online

Functional pearls online:

Linear, Bounded, Functional Pretty-Printing

S. Doaitse Sweirstra, Olaf Chitil. 2009.

Bidirectionalization for Free!

Janis Voigtländer. 2009.

Much Ado about Two: A Pearl on Parallel Prefix Computation

Janis Voigtländer. 2008.

Clowns to the Left of me, Jokers to the Right: Dissecting Data Structures

Conor McBride. 2008.

Functional Pearl: The Great Escape: Or how to jump the border without getting caught

David Herman. 2007.

Scrap Your Zippers

Michael Adams. 2007.

A type-correct, stack-safe, provably correct expression compiler in Epigram

James McKinna and Joel Wright. 2006.

Applicative Programming with Effects

Conor McBride and Ross Paterson. 2006.

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.

Pickler Combinators

Andrew Kennedy. 2004.

Composing fractals

Mark P. Jones. 2004.

Enumerating the strings of regular languages

M. Douglas McIlroy. 2004.

Functional satisfaction

Luc Maranget. 2004. (More info).

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. (Also here).

Parsing permutation phrases

Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004.

Concurrent distinct choices

Sergio Antoy and Michael Hanus. 2004.

Functional chart parsing of context-free grammars

Peter Ljunglf. 2004.

Type-Safe Cast

Stephanie Weirich. 2004.

Pickler Combinators

Andrew J. Kennedy. 2004.

Parallel Parsing Processes

Koen Claessen. 2004.

Derivation of a logarithmic time carry lookahead addition circuit

John O'Donnell and Gudula Runger. 2004. (ACM) (JFP) (Homepage).

Producing all ideals of a forest, functionally

Jean-Christophe Fillitre and Franois Pottier. 2003.

Trouble shared is trouble halved

Richard Bird, Ralf Hinze. 2003

Formatting: a class act

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.

Monads for Incremental Computing

Magnus Carlsson. 2002.

Haskell does it with class: Functorial unparsing

Ralf Hinze. 2001.

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.

Explaining binomial heaps

Ralf Hinze. 1999.

Power series, power serious

M. Douglas McIlroy. 1999.

Red-black trees in a functional setting

Chris Okasaki. 1999.

Proof-directed debugging

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

A pointless derivation of radix sort

Jeremy Gibbons. 1999.

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.

The Zipper

Gerard Huet. 1997. (See also The Haskell Wikibook).

Lazy wheel sieves and spirals of primes

Colin Runciman. 1997.

Three algorithms on Braun trees

Chris Okasaki. 1997.

The Third Homomorphism Theorem

Jeremy Gibbons. 1996.

Back to Basics: Deriving Representation Changers Functionally.

Graham Hutton, Erik Meijer. 1996.

Drawing Trees

Andrew J. Kennedy. 1996.

Deriving Tidy Drawings of Trees

Jeremy Gibbons. 1996. (See also the research report).

Efficient Sets - A Balancing Act

Stephen Adams. 1993. (Data.Set).

Potential Pearls

Unpublished pearls.

Typed Quote/AntiQuote

Ralf Hinze. Unpublished work in progress.

α-conversion is easy

Thorsten Altenkirch. Unpublished draft.

Offline

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

Functional Pearl: Streams and Unique Fixed Points

Ralf Hinze, ICFP 2008

Linear lambda calculus and PTIME-completeness

Harry G. Mairson. 2004.

Calculating the Sieve of Eratosthenes

Lambert Meertens. Journal of Functional Programming, 14(6):759-763, 2004. (slides)

Red-black trees with types

Stefan Kahrs. 2001. (JFP) (Code!)

On generating unique names

Lennart Augustsson, M Rittri, D Synek. 1994. (Rittri's homepage)

A Symmetric Set of Efficient List Operations.

Rob R. Hoogerwoord, 1992. (Hoogerwoord's homepage).

Finding celebrities: A lesson in functional programming

Richard Bird and Sharon Curtis. 2006. (See also).

A program to solve Sudoku

Richard Bird. 2006. (slides appear here, a Literate Haskell implementation by Graham Hutton based on this can be found here).

On tiling a chessboard

Richard Bird. 2004. (ACM)

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. (Bib).

The Last Tail.

Richard Bird. 1993. (Bib).

Two Greedy Algorithms

Richard Bird, 1992. (Bib).

On Removing Duplicates

Richard Bird. 1991. (Bib).