Difference between revisions of "Research papers/Functional pearls"

From HaskellWiki
Jump to navigation Jump to search
m (use open access doi.org links instead of preprints)
 
(109 intermediate revisions by 43 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 and at [http://www.icfpconference.org/index.html ICFP] and affiliated workshops.
   
  +
== History ==
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.
 
   
  +
The history of functional pearls is covered by:
;[http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]
 
:Richard Bird. ICFP 2006.
 
   
  +
* [http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]
;[http://portal.acm.org/ft_gateway.cfm?id=1159832&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Fifteen years of functional pearls]
 
:Richard Bird. ICFP 2006.
+
*: Richard Bird. ICFP 2006.
   
  +
* [http://portal.acm.org/ft_gateway.cfm?id=1159832&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Fifteen years of functional pearls]
;[http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl, forty years on]
 
:Mike Spivey, 2006.
+
*: Richard Bird. ICFP 2006.
   
  +
* [https://web.archive.org/web/20160311022831/http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl and forty years on]
=== Online ===
 
  +
*: Mike Spivey. 2006.
   
  +
* [http://www.brics.dk/RS/07/14/index.html On Barron and Strachey's Cartesian Product Function]
Functional pearls online:
 
  +
*: Olivier Danvy and Michael Spivey. July 2007
   
  +
There have been many functional pearls in JFP and and some others at
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf Enumerating the rationals]
 
  +
ICFP and the Haskell Workshop. There is also a collection of them in
:Jeremy Gibbons, David Lester and Richard Bird. 2006.
 
  +
[https://www.cs.ox.ac.uk/publications/publication2338-abstract.html The Fun of Programming].
   
  +
The pearls tend to concentrate on:
;[http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell]
 
:Martin Erwig and Steve Kollmansberger. 2006.
 
   
  +
* Examples of program calculation and proof
;[http://cms.brookes.ac.uk/staff/SharonCurtis/publications/marbles.ps.gz Marble mingling]
 
  +
* Neat presentations of new or old data structures
:Sharon Curtis. 2006.
 
  +
* 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].
;[http://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Strong Types for Relational Databases]
 
:Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)
 
   
  +
== Online ==
;[http://portal.acm.org/ft_gateway.cfm?id=1086390&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Backtracking, interleaving, and terminating monad transformers]
 
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005.
 
   
  +
Functional pearls available online.
;[http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate]
 
:James Cheney. 2005.
 
   
  +
;2023
;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages]
 
  +
* [https://doi.org/10.1145/3607853 More Fixpoints!] - Joachim Breitner.
:M. Douglas McIlroy. 2004.
 
  +
* [https://doi.org/10.1145/3607849 HasChor: Functional Choreographic Programming for All] - Gan Shen, Shun Kashiwa, Lindsey Kuper.
   
  +
;2022
;[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]
 
  +
* [https://doi.org/10.1145/3547640 'do' Unchained: Embracing Local Imperativity in a Purely Functional Language] - Sebastian Ullrich, Leonardo de Moura.
:Oleg Kiselyov, Chung-chieh Shan. 2004. ([http://www.cs.rutgers.edu/~ccshan/prepose/p1214-kiselyov.pdf also here])
 
  +
* [https://doi.org/10.1145/3547624 Monadic Compiler Calculation] - Patrick Bahr, Graham Hutton.
  +
* [https://doi.org/10.1145/3547621 Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structured Control Flow] - Norman Ramsey.
   
  +
;2021
;[http://www.cs.chalmers.se/~rjmh/Globals.ps Global variables in Haskell]
 
  +
* [https://www.cs.nott.ac.uk/~pszgmh/123.pdf It’s Easy As 1,2,3] - Graham Hutton.
:John Hughes. 2004. ([http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=241773 JFP])
 
  +
* [https://doi.org/10.1145/3471874.3472984 Design Patterns for Parser Combinators] - Jamie Willis, Nicolas Wu.
   
  +
;2020
;[http://portal.acm.org/ft_gateway.cfm?id=1017477&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 I am not a number -- I am a free variable]
 
  +
* [https://dl.acm.org/doi/10.1145/3408974 Achieving high-performance the functional way] - Bastian Hagedorn, Johannes Lenfers, Thomas Kœhler, Xueying Qin, Sergei Gorlatch, Michel Steuwer.
:Conor McBride, James McKinna. 2004.
 
  +
* [https://doi.org/10.1145/3408990 Parsing with zippers] - Pierce Darragh, Michael D. Adams
  +
* [https://doi.org/10.1145/3408998 Separation Logic for Sequential Programs] - Arthur Charguéraud
  +
* [https://doi.org/10.1145/3409004 Strong Functional Pearl: Harper's Regular-Expression Matcher in Cedille] - Aaron Stump, Chris Jenkins, Stephan Spahn, Colin McDonald
  +
* [https://dl.acm.org/doi/10.1145/3409006 The simple essence of algebraic subtyping: principal type inference with subtyping made easy] - Lionel Parreaux
  +
* [https://doi.org/10.1145/3406088.3409024 A Graded Monad for Deadlock-Free Concurrency] - Andrej Ivašković, Alan Mycroft
  +
* [https://dl.acm.org/doi/10.1145/3406088.3409026 Finger Trees explained anew, and slightly simplified] - Koen Claessen.
  +
* [https://doi.org/10.1145/3406088.3409015 Stitch: The Sound Type-Indexed Type Checker] - Richard A. Eisenberg
  +
* [https://doi.org/10.1145/3406088.3409019 Type Your Matrices for Great Good: A Haskell Library of Typed Matrices and Applications] - Armando João Isaías Ferreira dos Santos, Jose Nuno Oliveira
  +
;2018
  +
* [http://www.cs.ox.ac.uk/jeremy.gibbons/publications/proyo.pdf What You Needa Know about Yoneda: Profunctor Optics and the Yoneda Lemma] - Guillaume Boisseau and Jeremy Gibbons.
   
  +
;2017
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform]
 
  +
* [https://jyp.github.io/pdf/Prettiest.pdf A Pretty But Not Greedy Printer] - Jean-Philippe Bernardy.
:Richard Bird and Shin-Cheng Mu. 2004.
 
  +
* [https://eprint.ncl.ac.uk/file_store/production/239461/EF82F5FE-66E3-4F64-A1AC-A366D1961738.pdf Algebraic Graphs with Class] - Andrey Mokhov.
  +
* [https://lemonidas.github.io/pdf/urns.pdf Ode on a Random Urn] - Leonidas Lampropoulos, Antal Spector-Zabusky and Kenneth Foner.
   
  +
;2016
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases]
 
  +
* [http://homes.sice.indiana.edu/ccshan/rational/pearl.pdf Deriving a Probability Density Calculator] - Wazim Mohammed Ismail and Chung-chieh Shan.
:Arthur Baars, Andres L�h and S. Doaitse Swierstra. 2004.
 
  +
* [http://www.iis.sinica.edu.tw/~scm/pub/queueing-glueing.pdf Queueing and Glueing for Optimal Partitioning] - Shin-Cheng Mu, Yu-Hsi Chiang and Yu-Han Lyu.
  +
* [http://www.cs.ox.ac.uk/jeremy.gibbons/publications/delivery.pdf Free Delivery] - Jeremy Gibbons.
  +
* [https://www-ps.informatik.uni-kiel.de/~sad/icfp2016-preprint.pdf All Sorts of Permutations] - Jan Christiansen, Nikita Danilenko and Sandra Dylus.
   
  +
;2015
;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices]
 
  +
* [https://www.fceia.unr.edu.ar/~mauro/pubs/smartviews/smartviews.pdf A Smart View on Datatypes] - Mauro Jaskelioff and Exequiel Rivas.
:Sergio Antoy and Michael Hanus. 2004.
 
  +
* [http://www.cse.chalmers.se/~russo/publications_files/pearl-russo.pdf Two Can Keep a Secret and If One of Them Uses Haskell] - Alejandro Russo.
   
  +
;2013.
;[http://www.ling.gu.se/~peb/pubs/p04-chart-pearl.pdf Functional chart parsing of context-free grammars]
 
  +
* [http://web.cecs.pdx.edu/~mpj/snakecube/ Solving the Snake Cube Puzzle in Haskell] - Mark P. Jones.
:Peter Ljungl�f. 2004.
 
   
  +
;2012
;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast]
 
  +
* [http://www.cs.tufts.edu/~nr/cs257/archive/mike-spivey/maybe-not-enough.pdf When Maybe is not good enough] - Michael Spivey.
:Stephanie Weirich. 2004.
 
  +
* [http://ozark.hendrix.edu/~yorgey/pub/monoid-pearl.pdf Monoids: Theme and Variations] - Brent Yorgey.
   
  +
;2011
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]
 
  +
* [http://dx.doi.org/10.1017/S0956796810000341 The Hough transform] - Maarten Fokkinga.
:Andrew J. Kennedy. 2004.
 
  +
* [http://www.staff.science.uu.nl/~swier004/publications/2011-jfp.pdf Sorted. Verifying the Problem of the Dutch National Flag in Agda] - Wouter Swierstra.
  +
* [http://www.cs.ox.ac.uk/people/ralf.hinze/publications/Quote.pdf Typed Quote/Antiquote - Or: Compile-time Parsing] - Ralf Hinze.
   
  +
;2010
;[http://www.cs.chalmers.se/~koen/pubs/jfp04-parser.ps Parallel Parsing Processes]
 
  +
* [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/pearl.pdf Every Bit Counts] - Dimitrios Vytiniotis and Andrew Kennedy.
:Koen Claessen. 2004.
 
  +
* [http://sebfisch.github.io/haskell-regexp/regexp-play.pdf A Play on Regular Expressions] - Sebastian Fischer. Frank Huch and Thomas Wilke.
   
  +
;2009
;[http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest, functionally]
 
  +
* [http://dx.doi.org/10.1145/1596550.1596577 Free Theorems Involving Type Constructor Classes] - Janis Voigtländer.
:Jean-Christophe Filli�tre and Fran�ois Pottier. 2003.
 
  +
* [http://www.cs.kent.ac.uk/pubs/2009/2847/content.pdf Linear, Bounded and Functional Pretty-Printing] - S. Doaitse Swierstra and Olaf Chitil.
  +
* [http://dx.doi.org/10.1145/1480881.1480904 Bidirectionalization for Free!] - Janis Voigtländer.
  +
* [http://web.engr.oregonstate.edu/~walkiner/papers/jfp09-hagl.pdf A Domain-Specific Language for Experimental Game Theory] - Eric Walkingshaw and Martin Erwig.
   
  +
;2008
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf Trouble shared is trouble halved]
 
  +
* [https://web.archive.org/web/20160527131614/https://www.staff.science.uu.nl/~swier004/Publications/DataTypesALaCarte.pdf Functional Pearl: Data Types A La Carte] - Wouter Swierstra.
:Richard Bird, Ralf Hinze. 2003
 
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP08.pdf Functional Pearl: Streams and Unique Fixed Points] - Ralf Hinze.
  +
* [http://dx.doi.org/10.1145/1411204.1411220 Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time] - Fritz Henglein.
  +
* [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.8486&rep=rep1&type=pdf Undoing Dynamic Typing] - Nick Benton.
  +
* [http://dx.doi.org/10.1145/1328438.1328445 Much Ado about Two: A Pearl on Parallel Prefix Computation] - Janis Voigtländer.
  +
* [http://strictlypositive.org/CJ.pdf Clowns to the Left of me and Jokers to the Right: Dissecting Data Structures]: Conor McBride.
   
  +
;2007
;[http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz A fresh look at binary search trees]
 
  +
* [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.
:Ralf Hinze. 2002.
 
  +
* [https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2007.pdf Scrap Your Zippers]
  +
*: Michael Adams. (superseded by the [https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2010.pdf WGP 2010 version].)
   
  +
;2006
;[http://www.cs.nott.ac.uk/~gmh/countdown.pdf The countdown problem]
 
  +
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.4086 A type-correct, stack-safe and provably correct expression compiler in Epigram] - James McKinna and Joel Wright.
:Graham Hutton. 2002.
 
  +
* [http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf Applicative Programming with Effects] - Conor McBride and Ross Paterson.
  +
* [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/rationals.pdf Enumerating the rationals] - Jeremy Gibbons, David Lester and Richard Bird.
  +
* [http://www.cs.tufts.edu/~nr/cs257/archive/richard-bird/sudoku.pdf A program to solve Sudoku]
  +
*: Richard Bird. ([http://icfp06.cs.uchicago.edu/bird-talk.pdf slides]; an [http://www.cs.nott.ac.uk/~gmh/sudoku.lhs implementation] in Literate Haskell by Graham Hutton.)
   
  +
* [http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell] - Martin Erwig and Steve Kollmansberger.
;[http://pdos.csail.mit.edu/papers/packrat-parsing:icfp02.pdf Packrat parsing: simple, powerful, lazy, linear time, functional pearl]
 
  +
* [http://dx.doi.org/10.1017/S095679680300474X Marble mingling] - Sharon Curtis.
:Bryan Ford. 2002.
 
  +
* [http://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Strong Types for Relational Databases] - Alexandra Silva and Joost Visser.
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/3E79673B3E7EA223532194DFBFF69569/S0956796805005678a.pdf/functional_pearls_finding_celebrities_a_lesson_in_functional_programming.pdf Finding celebrities: A lesson in functional programming] - Richard Bird and Sharon Curtis.
   
  +
;2005
;[http://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms]
 
  +
* [http://okmij.org/ftp/papers/LogicT.pdf Backtracking, interleaving and and terminating monad transformers] - Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry.
:Richard Bird. 2001.
 
  +
* [http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate] - James Cheney.
   
  +
;2004
;[http://eprints.ouls.ox.ac.uk/archive/00000862/01/bird_2001.pdf Maximum marking problems]
 
  +
* [http://dx.doi.org/10.1017/S0956796804005209 Pickler Combinators] - Andrew Kennedy.
:Richard Bird. 2001.
 
  +
* [http://web.cecs.pdx.edu/~mpj/pubs/composing-fractals.pdf Composing fractals] - Mark P. Jones.
  +
* [http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages] - M. Douglas McIlroy.
  +
* [http://www.kestrel.edu/home/people/meertens/publications/papers/Calculating_the_Sieve_of_Eratosthenes.pdf Calculating the Sieve of Eratosthenes] - Lambert Meertens. ([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. ([http://pauillac.inria.fr/~maranget/enum/index.html more info].)
;[http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz Weaving a web]
 
:Ralf Hinze and Johan Jeuring. 2001.
 
   
  +
* [http://portal.acm.org/ft_gateway.cfm?id=1017481&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Implicit configurations--or and type classes reflect the values of types] - Oleg Kiselyov and Chung-chieh Shan.
;[http://www.brics.dk/RS/01/16/BRICS-RS-01-16.pdf Normalization by evaluation with typed abstract syntax]
 
  +
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global variables in Haskell] - John Hughes.
:Olivier Danvy, Morten Rhiger and Kristoffer H. Rose. 2001.
 
  +
* [http://portal.acm.org/ft_gateway.cfm?id=1017477&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 I am not a number -- I am a free variable] - Conor McBride and James McKinna.
  +
* [http://dx.doi.org/10.1017/S0956796804005118 Inverting the Burrows Wheeler transform] - Richard Bird and Shin-Cheng Mu. (also [http://web.comlab.ox.ac.uk/people/Richard.Bird/online/BirdMu2004Inverting.pdf here].)
   
  +
* [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases] - Arthur Baars and Andres Loh and S. Doaitse Swierstra.
;[http://www.brics.dk/RS/01/10/BRICS-RS-01-10.ps.gz Do we need dependent types?]
 
  +
* [http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices] - Sergio Antoy and Michael Hanus.
:Daniel Fridlender and Mia Indrika. 2001.
 
  +
* [http://dx.doi.org/10.1017/S0956796804005106 Functional chart parsing of context-free grammars] - Peter Ljunglf.
  +
* [http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast] - Stephanie Weirich.
  +
* [http://www.cse.chalmers.se/edu/course/afp/Papers/parser-claessen.pdf Parallel Parsing Processes] - Koen Claessen.
  +
* [http://dx.doi.org/10.1017/S0956796804005180 Derivation of a logarithmic time carry lookahead addition circuit] - John O'Donnell and Gudula Runger.
  +
* [http://pages.cs.brandeis.edu/~mairson/Papers/jfp02.pdf Linear lambda calculus and PTIME-completeness] - Harry G. Mairson.
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/44A9D4F4D9AF0D8380D5E573E7E7F885/S095679680400512Xa.pdf/functional_pearl_on_tiling_a_chessboard.pdf On tiling a chessboard] - Richard Bird.
   
  +
;2003
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-99-4.ps.gz Perfect trees and bit-reversal permutations]
 
  +
* [http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest and functionally] - Jean-Christophe Filliatre and Francois Pottier.
:Ralf Hinze. 2000.
 
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/HW03.pdf Trouble shared is trouble halved] - Richard Bird and Ralf Hinze.
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/Format.ps.gz Formatting: a class act] - Ralf Hinze.
   
  +
;2002
;[http://spivey.oriel.ox.ac.uk/mike/bfs/bfs.ps Combinators for breadth-first search]
 
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/SearchTree.ps.gz A fresh look at binary search trees] - Ralf Hinze.
:Michael Spivey. 2000
 
  +
* [http://www.cs.nott.ac.uk/~gmh/countdown.pdf The countdown problem] - Graham Hutton.
  +
* [http://pdos.csail.mit.edu/papers/packrat-parsing:icfp02.pdf Packrat parsing: simple, powerful, lazy, linear time and functional pearl] - Bryan Ford.
  +
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing] - Magnus Carlsson.
   
  +
;2001
;[http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design]
 
  +
* [http://www.cs.nott.ac.uk/~gmh/wgp01/hinze-paper.pdf Haskell does it with class: Functorial unparsing] - Ralf Hinze.
:Chris Okasaki. 2000.
 
  +
* [http://dx.doi.org/10.1017/S0956796801003914 Unfolding pointer algorithms] - Richard Bird.
  +
* [http://dx.doi.org/10.1017/S0956796801004038 Maximum marking problems] - Richard Bird.
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/TheWeb.ps.gz Weaving a web] - Ralf Hinze and Johan Jeuring.
  +
* [http://www.brics.dk/RS/01/16/BRICS-RS-01-16.pdf Normalization by evaluation with typed abstract syntax] - Olivier Danvy, Morten Rhiger and Kristoffer H. Rose.
  +
* [http://www.brics.dk/RS/01/10/BRICS-RS-01-10.ps.gz Do we need dependent types?] - Daniel Fridlender and Mia Indrika.
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/632BDF7BE8CD1F6EAEDEA37E6046E4A1/S0956796801004026a.pdf/redblack_trees_with_types.pdf Red-black trees with types] - Stefan Kahrs. ([http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html code].)
   
  +
;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/BitReversal.ps.gz Perfect trees and bit-reversal permutations] and 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.
:Ralf Hinze. 2000.
 
  +
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2420 Combinators for breadth-first search] - Michael Spivey.
  +
* [https://web.archive.org/web/20120321020542/http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design] - Chris Okasaki.
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers] - Ralf Hinze.
  +
* [http://www.cis.upenn.edu/~bcpierce/papers/rsr.ps Recursive subtyping revealed] - Vladimir Gapeyev, Michael Y. Levin and Benjamin C. Pierce.
  +
* [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.493&rep=rep1&type=pdf Composing contracts: an adventure in financial engineering] - Simon Peyton Jones, Jean-Marc Eber and Julian Seward.
   
  +
;1999
;[http://www.cis.upenn.edu/~bcpierce/papers/rsr.ps Recursive subtyping revealed]
 
  +
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039 A poor man's concurrency monad] - Koen Claessen.
:Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. 2000.
 
  +
* [http://www.cs.ox.ac.uk/ralf.hinze/publications/BinomialHeaps/index.html Explaining binomial heaps] - Ralf Hinze.
  +
* [http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series and power serious] - M. Douglas McIlroy.
  +
* [http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps Red-black trees in a functional setting] - Chris Okasaki.
  +
* [http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]
  +
*: Robert Harper. (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.
;[http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/contracts-icfp.ps.gz Composing contracts: an adventure in financial engineering]
 
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.
 
   
  +
;1998
;[http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps A poor man's concurrency monad]
 
  +
* [http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell] - Graham Hutton and Erik Meijer.
:Koen Claessen. 1999.
 
  +
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6891 Polytypic unification] - Patrik Jansson and Johan Jeuring.
  +
* [http://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf Diets for fat sets] - Martin Erwig.
  +
* [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.
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/991084CDC1A348354224F893E2BD1D0C/S0956796897002931a.pdf/meertens_number.pdf Meertens number] - Richard Bird.
   
  +
;1997
;[http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series, power serious]
 
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/DB0CF71E6B3D975D1F171C02336F3FA3/S0956796897002736a.pdf/functional-pearl-on-merging-and-selection.pdf On merging and selection]
:M. Douglas McIlroy. 1999.
 
  +
*: Richard Bird. (see also [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/merging.ps.gz More on Merging and Selection].)
   
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/23D5C1B90A6B00A5D87239054FEDC8CF/S0956796897002803a.pdf/functional-pearl-on-building-trees-with-minimum-height.pdf On building trees with minimum height] - Richard Bird.
;[http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]
 
  +
* [http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper]
: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]).
 
  +
*: Gerard Huet. (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.
;[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell]
 
  +
* [https://web.archive.org/web/20120314024849/http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees] - Chris Okasaki.
:Graham Hutton and Erik Meijer . 1998.
 
   
  +
;1996
;[http://www.cs.chalmers.se/~patrikj/poly/unify/PolytypicUnification.ps Polytypic unification]
 
  +
* [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem] - Jeremy Gibbons.
:Patrik Jansson and Johan Jeuring. 1998.
 
  +
* [http://www.cs.nott.ac.uk/~gmh/basics.pdf Back to Basics: Deriving Representation Changers Functionally] - Graham Hutton and Erik Meijer.
  +
* [http://dx.doi.org/10.1017/S0956796800001830 Drawing Trees] - Andrew J. Kennedy.
  +
* [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]
  +
*: Jeremy Gibbons. (see also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report].)
   
  +
;1994
;[http://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf Diets for fat sets]
 
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/763DE73EB4761FDF681A613BE0E98443/S0956796800000988a.pdf/functional_pearl_on_generating_unique_names.pdf On generating unique names] - Lennart Augustsson, Mikael Rittri and Dan Synek.
:Martin Erwig. 1998.
 
   
  +
;1993
;[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?]
 
  +
* [http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act]
:Chris Okasaki. 1998.
 
  +
*: Stephen Adams. (<code>Data.Set</code> [http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html code].)
   
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/CC6079CCEC88883F6C10DFB12908795F/S0956796800000630a.pdf/functional_pearls_the_last_tail.pdf The Last Tail] - Richard Bird.
;[http://citeseer.ist.psu.edu/runciman97lazy.html Lazy wheel sieves and spirals of primes]
 
:Colin Runciman. 1997.
 
   
  +
;1992
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem]
 
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/A77930CC2C68694EBB93964AF16D06D0/S0956796800000526a.pdf/functional_pearls_a_symmetric_set_of_efficient_list_operations.pdf A Symmetric Set of Efficient List Operations]
:Jeremy Gibbons. 1996.
 
  +
*: Rob R. Hoogerwoord. (Hoogerwoord's [https://venus.tue.nl/ep-cgi/ep_publ.opl?taal=NL&fac_id=92&rn=19840694 homepage].)
   
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/E55EFDCCB071BBE9FFE0F6543C1BCBA1/S0956796800000368a.pdf/functional_pearls_two_greedy_algorithms.pdf Two Greedy Algorithms] - Richard Bird.
;[http://www.cs.nott.ac.uk/~gmh/basics.pdf Back to Basics: Deriving Representation Changers Functionally].
 
:Graham Hutton, Erik Meijer. 1996.
 
   
  +
;1991
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees]
 
  +
* [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/2CC831E0F77C77E86DD1E9AF165DECEE/S0956796800020074a.pdf/functional_pearls_on_removing_duplicates.pdf On Removing Duplicates] - Richard Bird.
:Drawing Trees. 1996.
 
   
  +
;1988
;[http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]
 
  +
* [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages] - F. Warren Burton.
:Jeremy Gibbons. 1996. (See also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report]).
 
   
=== Offline ===
+
== Potential pearls ==
   
  +
Unpublished pearls.
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section!
 
   
  +
* [http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf α-conversion is easy]
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming]
 
  +
*: Thorsten Altenkirch. (unpublished draft.)
:Richard Bird and Sharon Curtis. 2006.
 
   
  +
<!--
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=451101 A program to solve Sudoku]
 
  +
== Offline ==
:Richard Bird. 2006.
 
   
  +
These appear not to be available online, unfortunately. If you know where they live, please link and and move into the 'online' section!
;[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 Rnger. 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])
 
 
;[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]
 
:Stefan Kahrs. 2001. ([http://journals.cambridge.org/article_S0956796801004026 also])
 
 
;[http://www.journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44229 Explaining binomial heaps]
 
:Ralf Hinze. 1999.
 
 
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44238 A pointless derivation of radix sort]
 
:Jeremy Gibbons. 1999.
 
 
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44274 Red-black trees in a functional setting]
 
:Chris Okasaki. 1999.
 
 
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44142 Meertens number]
 
:Richard Bird. 1998.
 
 
;[http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=44092 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]).
 
 
;[http://journals.cambridge.org/article_S0956796897002803 On building trees with minimum height]
 
:Richard Bird. 1997.
 
 
;[http://portal.acm.org/citation.cfm?id=969872 The Zipper]
 
:Grard 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.
 
: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.
 
   
 
[[Category:Research]] [[Category:Tutorials]]
 
[[Category:Research]] [[Category:Tutorials]]

Latest revision as of 16:50, 6 February 2024

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 and at ICFP and affiliated workshops.

History

The history of functional pearls is covered by:

There have been many functional pearls in JFP and 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 available online.

2023
2022
2021
2020
2018
2017
2016
2015
2013.
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1994
1993
1992
1991
1988

Potential pearls

Unpublished pearls.