Difference between revisions of "Research papers/Functional pearls"
Jump to navigation
Jump to search
(→Online: added author for Drawing Trees) |
MattRussell (talk | contribs) |
||
| Line 11: | Line 11: | ||
;[http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl, forty years on] |
;[http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl, forty years on] |
||
:Mike Spivey, 2006. |
:Mike Spivey, 2006. |
||
| + | |||
| + | ;[http://www.brics.dk/RS/07/14/index.html 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 |
There have been some 64 functional pearls in JFP, and some others at |
||
Revision as of 09:19, 22 August 2008
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:
- 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, And 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.
- 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!
- 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).
- 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).