Research papers/Functional pearls
From HaskellWiki
(Fixed broken links to papers by Ralf Hinze) 

(18 intermediate revisions by 12 users not shown) 
Revision as of 18:30, 11 June 2012
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 many 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
Some advice on writing pearls for JFP is available in this editorial.
1 Online
Functional pearls online:
 Every Bit Counts
 Dimitrios Vytiniotis, Andrew Kennedy. 2010.
 Combining Syntactic and Semantic Bidirectionalization
 Janis Voigtländer, Zhenjiang Hu, Kazutaka Matsuda, Meng Wang. 2010.
 Free Theorems Involving Type Constructor Classes
 Janis Voigtländer. 2009.
 Linear, Bounded, Functional PrettyPrinting
 S. Doaitse Swierstra, Olaf Chitil. 2009.
 Bidirectionalization for Free!
 Janis Voigtländer. 2009.
 Functional Pearl: Streams and Unique Fixed Points
 Ralf Hinze, ICFP 2008
 Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time
 Fritz Henglein. 2008
 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. Superseded by the WGP 2010 version.
 A typecorrect, stacksafe, 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.
 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).
 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, Chungchieh 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.
 Calculating the Sieve of Eratosthenes
 Lambert Meertens. Journal of Functional Programming, 14(6):759763, 2004. (slides)
 Functional satisfaction
 Luc Maranget. 2004. (More info).
 Implicit configurationsor, type classes reflect the values of types
 Oleg Kiselyov, Chungchieh 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 ShinCheng 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 contextfree grammars
 Peter Ljunglf. 2004.
 TypeSafe Cast
 Stephanie Weirich. 2004.
 Pickler Combinators
 Andrew J. Kennedy. 2004.
 [www.cse.chalmers.se/edu/course/afp/Papers/parserclaessen.pdf 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).
 Linear lambda calculus and PTIMEcompleteness
 Harry G. Mairson. 2004.
 Producing all ideals of a forest, functionally
 JeanChristophe Filliatre and Francois 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 bitreversal permutations, a revision of Technical Report IAITR994
 Ralf Hinze. 2000.
 Combinators for breadthfirst search
 Michael Spivey. 2000
 BreadthFirst 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, JeanMarc 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.
 Redblack trees in a functional setting
 Chris Okasaki. 1999.
 Proofdirected debugging
 Robert Harper. 1999. (see also Proofdirected debugging: revisited for a firstorder 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 higherorder functions for parsing or Why would anyone ever want to use a sixthorder 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.
 Undoing Dynamic Typing
 Nick Benton. 2008.
 Deriving Tidy Drawings of Trees
 Jeremy Gibbons. 1996. (See also the research report).
 Efficient Sets  A Balancing Act
 Stephen Adams. 1993. (Data.Set).
2 Potential Pearls
Unpublished pearls.
 Typed Quote/AntiQuote
 Ralf Hinze. Unpublished work in progress.
 αconversion is easy
 Thorsten Altenkirch. Unpublished draft.
3 Offline
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section!
 Redblack 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).
 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).