Difference between revisions of "Research papers/Functional pearls"

From HaskellWiki
Jump to navigation Jump to search
(An attempt at an exhaustive collection of online functional pearls)
 
m (Fix some more links)
(85 intermediate revisions by 31 users not shown)
Line 1: Line 1:
  +
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 [http://journals.cambridge.org/action/displayJournal?jid=JFP The Journal of Functional Programming], and at [http://www.icfpconference.org/index.html ICFP] and affiliated workshops.
   
  +
The history of functional pearls is covered by:
−
Functional pearls are elegant, instructive examples of functional programming,
  
−
traditionally appearing in [http://www.cambridge.org/journals/JFP/ The Journal of Functional Programming], and at
  
−
[http://www.icfpconference.org/index.html ICFP] and affiliated workshops.
  
   
 
;[http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]
  
;[http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]
Line 12: 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 many functional pearls in JFP, and some others at
  +
ICFP and the Haskell Workshop. There is also a collection of them in
  +
[https://www.cs.ox.ac.uk/publications/publication2338-abstract.html 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 [http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/ editorial].
   
 
=== Online ===
  
=== Online ===
Line 17: Line 31:
 
Functional pearls online:
  
Functional pearls online:
   
  +
;[http://web.cecs.pdx.edu/~mpj/snakecube/ Solving the Snake Cube Puzzle in Haskell]
−
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf Enumerating the rationals]
  
  +
:Mark P. Jones. 2013
  +
  +
;[http://spivey.oriel.ox.ac.uk/wiki/images/0/06/Maybe.pdf When Maybe is not good enough]
  +
:Michael Spivey. 2012
  +
  +
;[http://ozark.hendrix.edu/~yorgey/pub/monoid-pearl.pdf Monoids: Theme and Variations]
  +
:Brent Yorgey. 2012.
  +
  +
;[http://dx.doi.org/10.1017/S0956796810000341 The Hough transform]
  +
:Maarten Fokkinga. 2011.
  +
  +
;[http://www.staff.science.uu.nl/~swier004/Publications/DutchNationalFlag.pdf Sorted. Verifying the Problem of the Dutch National Flag in Agda]
  +
:Wouter Swierstra. 2011.
  +
  +
;[http://www.cs.ox.ac.uk/people/ralf.hinze/publications/Quote.pdf Typed Quote/Antiquote - Or: Compile-time Parsing]
  +
:Ralf Hinze. 2011.
  +
  +
;[http://research.microsoft.com/en-us/people/dimitris/every-bit-counts.pdf Every Bit Counts]
  +
:Dimitrios Vytiniotis, Andrew Kennedy. 2010.
  +
  +
;[http://sebfisch.github.io/haskell-regexp/regexp-play.pdf A Play on Regular Expressions]
  +
:Sebastian Fischer. Frank Huch, Thomas Wilke. 2010.
  +
  +
;[http://dx.doi.org/10.1145/1596550.1596577 Free Theorems Involving Type Constructor Classes]
  +
:Janis Voigtländer. 2009.
  +
  +
;[http://www.cs.kent.ac.uk/pubs/2009/2847/content.pdf Linear, Bounded, Functional Pretty-Printing]
  +
:S. Doaitse Swierstra, Olaf Chitil. 2009.
  +
  +
;[http://dx.doi.org/10.1145/1480881.1480904 Bidirectionalization for Free!]
  +
:Janis Voigtländer. 2009.
  +
  +
;[https://www.staff.science.uu.nl/~swier004/Publications/DataTypesALaCarte.pdf Functional Pearl: Data Types A La Carte]
  +
:Wouter Swierstra, 2008
  +
  +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP08.pdf Functional Pearl: Streams and Unique Fixed Points]
  +
:Ralf Hinze, ICFP 2008
  +
  +
;[http://dx.doi.org/10.1145/1411204.1411220 Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time]
  +
:Fritz Henglein. 2008
  +
  +
;[http://dx.doi.org/10.1145/1328438.1328445 Much Ado about Two: A Pearl on Parallel Prefix Computation]
  +
:Janis Voigtländer. 2008.
  +
  +
;[http://strictlypositive.org/CJ.pdf Clowns to the Left of me, Jokers to the Right: Dissecting Data Structures]: Conor McBride. 2008.
  +
  +
;[http://www.ccs.neu.edu/home/dherman/research/papers/icfp07-great-escape.pdf Functional Pearl: The Great Escape: Or how to jump the border without getting caught]
  +
:David Herman. 2007.
  +
  +
;[https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2007.pdf Scrap Your Zippers]
  +
:Michael Adams. 2007. Superseded by the [https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2010.pdf WGP 2010 version].
  +
  +
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.4086 A type-correct, stack-safe, provably correct expression compiler in Epigram]
  +
:James McKinna and Joel Wright. 2006.
  +
  +
;[http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf Applicative Programming with Effects]
  +
:Conor McBride and Ross Paterson. 2006.
  +
  +
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/rationals.pdf Enumerating the rationals]
 
:Jeremy Gibbons, David Lester and Richard Bird. 2006.
  
:Jeremy Gibbons, David Lester and Richard Bird. 2006.
  +
  +
;[http://www.cs.tufts.edu/~nr/cs257/archive/richard-bird/sudoku.pdf A program to solve Sudoku]
  +
:Richard Bird. 2006. (slides [http://icfp06.cs.uchicago.edu/bird-talk.pdf appear here], a Literate Haskell implementation by Graham Hutton based on this can be found [http://www.cs.nott.ac.uk/~gmh/sudoku.lhs here]).
   
 
;[http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell]
  
;[http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell]
 
:Martin Erwig and Steve Kollmansberger. 2006.
 
:Martin Erwig and Steve Kollmansberger. 2006.
   
−
;[http://cms.brookes.ac.uk/staff/SharonCurtis/publications/marbles.ps.gz Marble mingling]
 +
;[http://dx.doi.org/10.1017/S095679680300474X Marble mingling]
 
:Sharon Curtis. 2006.
  
:Sharon Curtis. 2006.
   
Line 29: Line 105:
 
:Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)
  
:Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)
   
−
;[http://portal.acm.org/ft_gateway.cfm?id=1086390&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Backtracking, interleaving, and terminating monad transformers]
 +
;[http://okmij.org/ftp/papers/LogicT.pdf Backtracking, interleaving, and terminating monad transformers]
 
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005.
 
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005.
   
 
;[http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate]
  
;[http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate]
 
:James Cheney. 2005.
  
:James Cheney. 2005.
  +
  +
;[http://dx.doi.org/10.1017/S0956796804005209 Pickler Combinators]
  +
:Andrew Kennedy. 2004.
  +
  +
;[http://web.cecs.pdx.edu/~mpj/pubs/composing-fractals.pdf Composing fractals]
  +
:Mark P. Jones. 2004.
   
 
;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages]
  
;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages]
 
:M. Douglas McIlroy. 2004.
  
:M. Douglas McIlroy. 2004.
  +
  +
;[http://www.kestrel.edu/home/people/meertens/publications/papers/Calculating_the_Sieve_of_Eratosthenes.pdf Calculating the Sieve of Eratosthenes]
  +
:Lambert Meertens. Journal of Functional Programming, 14(6):759-763, 2004. ([http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting57/meertens-sieve.pdf slides])
  +
  +
;[http://pauillac.inria.fr/~maranget/enum/pearl.ps Functional satisfaction]
  +
:Luc Maranget. 2004. ([http://pauillac.inria.fr/~maranget/enum/index.html More info]).
   
 
;[http://portal.acm.org/ft_gateway.cfm?id=1017481&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Implicit configurations--or, type classes reflect the values of types]
  
;[http://portal.acm.org/ft_gateway.cfm?id=1017481&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Implicit configurations--or, type classes reflect the values of types]
−
:Oleg Kiselyov, Chung-chieh Shan. 2004. ([http://www.cs.rutgers.edu/~ccshan/prepose/p1214-kiselyov.pdf also here])
 +
:Oleg Kiselyov, Chung-chieh Shan. 2004.
   
−
;[http://www.cs.chalmers.se/~rjmh/Globals.ps Global variables in Haskell]
 +
;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global variables in Haskell]
 
:John Hughes. 2004. ([http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=241773 JFP])
  
:John Hughes. 2004. ([http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=241773 JFP])
   
Line 47: Line 135:
 
:Conor McBride, James McKinna. 2004.
 
:Conor McBride, James McKinna. 2004.
   
−
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform]
 +
;[http://dx.doi.org/10.1017/S0956796804005118 Inverting the Burrows Wheeler transform]
−
:Richard Bird and Shin-Cheng Mu. 2004.
 +
:Richard Bird and Shin-Cheng Mu. 2004. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/online/BirdMu2004Inverting.pdf Also here]).
   
−
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases]
 +
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases]
−
:Arthur Baars, Andres L�h and S. Doaitse Swierstra. 2004.
 +
:Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004.
   
 
;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices]
  
;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices]
 
:Sergio Antoy and Michael Hanus. 2004.
 
:Sergio Antoy and Michael Hanus. 2004.
   
−
;[http://www.ling.gu.se/~peb/pubs/p04-chart-pearl.pdf Functional chart parsing of context-free grammars]
 +
;[http://dx.doi.org/10.1017/S0956796804005106 Functional chart parsing of context-free grammars]
−
:Peter Ljungl�f. 2004.
 +
:Peter Ljunglf. 2004.
   
 
;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast]
  
;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast]
 
:Stephanie Weirich. 2004.
  
:Stephanie Weirich. 2004.
   
  +
;[http://www.cse.chalmers.se/edu/course/afp/Papers/parser-claessen.pdf Parallel Parsing Processes]
−
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]
  
−
:Andrew J. Kennedy. 2004.
 
−  
−
;[http://www.cs.chalmers.se/~koen/pubs/jfp04-parser.ps Parallel Parsing Processes]
  
 
:Koen Claessen. 2004.
  
:Koen Claessen. 2004.
  +
  +
;[http://dx.doi.org/10.1017/S0956796804005180 Derivation of a logarithmic time carry lookahead addition circuit]
  +
:John O'Donnell and Gudula Runger. 2004. ([http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=1030343 ACM]).
  +
  +
;[http://pages.cs.brandeis.edu/~mairson/Papers/jfp02.pdf Linear lambda calculus and PTIME-completeness]
  +
:Harry G. Mairson. 2004.
   
 
;[http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest, functionally]
  
;[http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest, functionally]
−
:Jean-Christophe Filli�tre and Fran�ois Pottier. 2003.
 +
:Jean-Christophe Filliatre and Francois Pottier. 2003.
   
−
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf Trouble shared is trouble halved]
 +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/HW03.pdf Trouble shared is trouble halved]
 
:Richard Bird, Ralf Hinze. 2003
  
:Richard Bird, Ralf Hinze. 2003
   
−
;[http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz A fresh look at binary search trees]
 +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/Format.ps.gz Formatting: a class act]
  +
:Ralf Hinze. 2003.
  +
  +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/SearchTree.ps.gz A fresh look at binary search trees]
 
:Ralf Hinze. 2002.
  
:Ralf Hinze. 2002.
   
Line 83: Line 177:
 
:Bryan Ford. 2002.
  
:Bryan Ford. 2002.
   
  +
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing]
−
;[http://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms]
  
  +
:Magnus Carlsson. 2002.
  +
  +
;[http://www.cs.nott.ac.uk/~gmh/wgp01/hinze-paper.pdf Haskell does it with class: Functorial unparsing]
  +
:Ralf Hinze. 2001.
  +
  +
  +
;[http://dx.doi.org/10.1017/S0956796801003914 Unfolding pointer algorithms]
 
:Richard Bird. 2001.
  
:Richard Bird. 2001.
   
−
;[http://eprints.ouls.ox.ac.uk/archive/00000862/01/bird_2001.pdf Maximum marking problems]
 +
;[http://dx.doi.org/10.1017/S0956796801004038 Maximum marking problems]
 
:Richard Bird. 2001.
 
:Richard Bird. 2001.
   
−
;[http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz Weaving a web]
 +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/TheWeb.ps.gz Weaving a web]
 
:Ralf Hinze and Johan Jeuring. 2001.
 
:Ralf Hinze and Johan Jeuring. 2001.
   
Line 98: Line 199:
 
:Daniel Fridlender and Mia Indrika. 2001.
  
:Daniel Fridlender and Mia Indrika. 2001.
   
−
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-99-4.ps.gz Perfect trees and bit-reversal permutations]
 +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/BitReversal.ps.gz Perfect trees and bit-reversal permutations], a revision of [http://www.cs.ox.ac.uk/ralf.hinze/publications/IAI-TR-99-4.ps.gz Technical Report IAI-TR-99-4]
 
:Ralf Hinze. 2000.
  
:Ralf Hinze. 2000.
   
Line 107: Line 208:
 
:Chris Okasaki. 2000.
  
:Chris Okasaki. 2000.
   
−
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers]
 +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers]
 
:Ralf Hinze. 2000.
  
:Ralf Hinze. 2000.
   
Line 116: Line 217:
 
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.
  
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.
   
−
;[http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps A poor man's concurrency monad]
 +
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039 A poor man's concurrency monad]
 
:Koen Claessen. 1999.
 
:Koen Claessen. 1999.
  +
  +
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/BinomialHeaps/index.html Explaining binomial heaps]
  +
:Ralf Hinze. 1999.
   
 
;[http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series, power serious]
  
;[http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series, power serious]
 
:M. Douglas McIlroy. 1999.
 
:M. Douglas McIlroy. 1999.
  +
  +
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps Red-black trees in a functional setting]
  +
:Chris Okasaki. 1999.
   
 
;[http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]
  
;[http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]
 
:Robert Harper. 1999. (see also [http://ropas.snu.ac.kr/~kwang/paper/06-jfp-yi.pdf Proof-directed debugging: revisited for a first-order version]).
  
:Robert Harper. 1999. (see also [http://ropas.snu.ac.kr/~kwang/paper/06-jfp-yi.pdf Proof-directed debugging: revisited for a first-order version]).
  +
  +
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/radix.ps.gz A pointless derivation of radix sort]
  +
:Jeremy Gibbons. 1999.
   
 
;[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell]
  
;[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell]
 
:Graham Hutton and Erik Meijer . 1998.
  
:Graham Hutton and Erik Meijer . 1998.
   
−
;[http://www.cs.chalmers.se/~patrikj/poly/unify/PolytypicUnification.ps Polytypic unification]
 +
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6891 Polytypic unification]
 
:Patrik Jansson and Johan Jeuring. 1998.
 
:Patrik Jansson and Johan Jeuring. 1998.
   
Line 134: Line 244:
 
:Martin Erwig. 1998.
 
:Martin Erwig. 1998.
   
−
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp98.ps Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?]
 +
;[https://www.cambridge.org/core/journals/journal-of-functional-programming/article/even-higher-order-functions-for-parsing-or-why-would-anyone-ever-want-to-use-a-sixth-order-function/AAAA5C5E29889CEBC5E944CC1080FE8D Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function?]
 
:Chris Okasaki. 1998.
  
:Chris Okasaki. 1998.
   
  +
;[http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper]
−
;[http://citeseer.ist.psu.edu/runciman97lazy.html Lazy wheel sieves and spirals of primes]
  
  +
:Gerard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]).
  +
  +
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096 Lazy wheel sieves and spirals of primes]
 
:Colin Runciman. 1997.
 
:Colin Runciman. 1997.
   
  +
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees]
−
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem]
  
  +
:Chris Okasaki. 1997.
  +
  +
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem]
 
:Jeremy Gibbons. 1996.
  
:Jeremy Gibbons. 1996.
   
Line 146: Line 262:
 
:Graham Hutton, Erik Meijer. 1996.
  
:Graham Hutton, Erik Meijer. 1996.
   
−
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees]
 +
;[http://dx.doi.org/10.1017/S0956796800001830 Drawing Trees]
−
:Drawing Trees. 1996.
 +
:Andrew J. Kennedy. 1996.
  +
  +
;[http://research.microsoft.com/~nick/newtrans.pdf Undoing Dynamic Typing]
  +
:Nick Benton. 2008.
   
−
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]
 +
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]
 
:Jeremy Gibbons. 1996. (See also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report]).
  
:Jeremy Gibbons. 1996. (See also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report]).
   
  +
;[http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act]
−
=== Offline ===
  
  +
:Stephen Adams. 1993. ([http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html Data.Set]).
   
  +
=== Potential Pearls ===
−
These appear not available online, unfortunately. If you know where they live, please link, and move into the 'online' section!
  
   
  +
Unpublished pearls.
−
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming]
  
−
:Richard Bird and Sharon Curtis. 2006.
  
   
  +
;[http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf α-conversion is easy]
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=451101 A program to solve Sudoku]
  
  +
:Thorsten Altenkirch. Unpublished draft.
−
:Richard Bird. 2006.
  
   
  +
=== Offline ===
−
;[http://www.journals.cambridge.org/action/displayAbstract?fromPage=online&aid=254705 On tiling a chessboard]
  
−
:Richard Bird. 2004.
  
−  
−
;[http://www.journals.cambridge.org/action/displayAbstract?fromPage=online&aid=254707 Linear lambda calculus and PTIME-completeness]
  
−
:Harry G. Mairson. 2004
  
−  
−
;[http://journals.cambridge.org/article_S0956796804005155 Functional satisfaction]
  
−
:Luc Maranget. 2004.
  
−  
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=254718 Derivation of a logarithmic time carry lookahead addition circuit]
  
−
:John T. O'Donnell and Gudula R�nger. 2004.
  
−  
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=254714 Composing fractals]
  
−
:Mark P. Jones. 2004.
  
−  
−
;[http://journals.cambridge.org/article_S0956796804005210 Calculating the Sieve of Eratosthenes]
  
−
:Lambert Meertens. 2004. ([http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/wg21/meeting57/meertens-sieve.pdf slides])
  
   
  +
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section!
−
;[http://journals.cambridge.org/article_S0956796802004367 Formatting: a class act]
  
−
:Ralf Hinze . 2003.
  
   
 
;[http://www.cs.kent.ac.uk/pubs/2001/1293/index.html Red-black trees with types]
  
;[http://www.cs.kent.ac.uk/pubs/2001/1293/index.html Red-black trees with types]
−
:Stefan Kahrs. 2001. ([http://journals.cambridge.org/article_S0956796801004026 also])
 +
:Stefan Kahrs. 2001. ([http://journals.cambridge.org/action/displayAbstract?aid=83905 JFP]) ([http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html Code!])
   
  +
;On generating unique names
−
;[http://www.journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44229 Explaining binomial heaps]
  
  +
:Lennart Augustsson, M Rittri, D Synek. 1994. ([http://www.cs.chalmers.se/~rittri/#publications Rittri's homepage])
−
:Ralf Hinze. 1999.
 
   
  +
;A Symmetric Set of Efficient List Operations.
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44238 A pointless derivation of radix sort]
  
  +
:Rob R. Hoogerwoord, 1992. ([https://venus.tue.nl/ep-cgi/ep_publ.opl?taal=NL&fac_id=92&rn=19840694 Hoogerwoord's homepage]).
−
:Jeremy Gibbons. 1999.
 
   
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44274 Red-black trees in a functional setting]
 +
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming]
  +
:Richard Bird and Sharon Curtis. 2006.
−
:Chris Okasaki. 1999.
 
   
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44142 Meertens number]
 +
;[http://journals.cambridge.org/action/displayAbstract?aid=254705 On tiling a chessboard]
  +
:Richard Bird. 2004. ([http://portal.acm.org/citation.cfm?id=1030333.1030336 ACM])
  +
  +
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44141 Meertens number]
 
:Richard Bird. 1998.
  
:Richard Bird. 1998.
   
−
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44092 On merging and selection]
 +
;[http://journals.cambridge.org/action/displayAbstract?aid=44091 On merging and selection]
−
:Richard Bird. 1997. (See also [http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/merging.ps.gz More on Merging and Selection]).
 +
:Richard Bird. 1997. (See also [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/merging.ps.gz More on Merging and Selection]).
   
−
;[http://journals.cambridge.org/article_S0956796897002803 On building trees with minimum height]
 +
;[http://journals.cambridge.org/action/displayAbstract?aid=44107 On building trees with minimum height]
  +
:Richard Bird. 1997. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird97:OnBuilding Bib]).
−
:Richard Bird. 1997.
 
−  
−
;[http://portal.acm.org/citation.cfm?id=969872 The Zipper]
  
−
:G�rard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]).
  
−  
−
;[http://journals.cambridge.org/article_S0956796897002876 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.
 
;The Last Tail.
  +
:Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird93:Last Bib]).
−
:Richard Bird. 1993.
  
−  
−
;A Symmetric Set of Efficient List Operations.
  
−
:Rob R. Hoogerwoord, 1992.
  
   
 
;Two Greedy Algorithms
  
;Two Greedy Algorithms
  +
:Richard Bird, 1992. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#Bird92:Two Bib]).
−
:Richard Bird, 1992.
  
   
 
;On Removing Duplicates
  
;On Removing Duplicates
  +
:Richard Bird. 1991. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#DBLP:journals/jfp/Bird91a Bib]).
−
:Richard Bird. 1991.
  
   
 
[[Category:Research]] [[Category:Tutorials]]
  
[[Category:Research]] [[Category:Tutorials]]

Revision as of 14:53, 26 October 2016

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.

Online

Functional pearls online:

Solving the Snake Cube Puzzle in Haskell
Mark P. Jones. 2013
When Maybe is not good enough
Michael Spivey. 2012
Monoids: Theme and Variations
Brent Yorgey. 2012.
The Hough transform
Maarten Fokkinga. 2011.
Sorted. Verifying the Problem of the Dutch National Flag in Agda
Wouter Swierstra. 2011.
Typed Quote/Antiquote - Or: Compile-time Parsing
Ralf Hinze. 2011.
Every Bit Counts
Dimitrios Vytiniotis, Andrew Kennedy. 2010.
A Play on Regular Expressions
Sebastian Fischer. Frank Huch, Thomas Wilke. 2010.
Free Theorems Involving Type Constructor Classes
Janis Voigtländer. 2009.
Linear, Bounded, Functional Pretty-Printing
S. Doaitse Swierstra, Olaf Chitil. 2009.
Bidirectionalization for Free!
Janis Voigtländer. 2009.
Functional Pearl: Data Types A La Carte
Wouter Swierstra, 2008
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 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.
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, 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.
Calculating the Sieve of Eratosthenes
Lambert Meertens. Journal of Functional Programming, 14(6):759-763, 2004. (slides)
Functional satisfaction
Luc Maranget. 2004. (More info).
Implicit configurations--or, type classes reflect the values of types
Oleg Kiselyov, Chung-chieh Shan. 2004.
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.
Parallel Parsing Processes
Koen Claessen. 2004.
Derivation of a logarithmic time carry lookahead addition circuit
John O'Donnell and Gudula Runger. 2004. (ACM).
Linear lambda calculus and PTIME-completeness
Harry G. Mairson. 2004.
Producing all ideals of a forest, functionally
Jean-Christophe 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 bit-reversal permutations, a revision of Technical Report IAI-TR-99-4
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.
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).

Potential Pearls

Unpublished pearls.

α-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!

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.
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).
Retrieved from "https://wiki.haskell.org/index.php?title=Research_papers/Functional_pearls&oldid=61239"