Research papers/Functional pearls

From HaskellWiki
Jump to navigation Jump to search

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.

And the pearls themselves:

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 Lh 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.
Producing all ideals of a forest, functionally
Jean-Christophe Fillitre and Franois 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 to be 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 Rnger. 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
Grard 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.