Difference between revisions of "Research papers/Functional pearls"
DaniilFrumin (talk | contribs) (→Online: sorted + another pearl) |
|||
(37 intermediate revisions by 19 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:// |
+ | 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: |
The history of functional pearls is covered by: |
||
Line 12: | Line 12: | ||
: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 |
||
+ | |||
⚫ | |||
ICFP and the Haskell Workshop. There is also a collection of them in |
ICFP and the Haskell Workshop. There is also a collection of them in |
||
− | [http:// |
+ | [http://web2.comlab.ox.ac.uk/oucl/publications/books/fop/ The Fun of Programming]. |
The pearls tend to concentrate on: |
The pearls tend to concentrate on: |
||
Line 21: | Line 24: | ||
* Neat presentations of new or old data structures |
* Neat presentations of new or old data structures |
||
* Interesting applications and techniques |
* 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 === |
||
Functional pearls online: |
Functional pearls online: |
||
+ | |||
+ | ;[http://web.cecs.pdx.edu/~mpj/snakecube/ Solving the Snake Cube Puzzle in Haskell] |
||
+ | :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://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf Monoids: Theme and Variations] |
||
+ | :Brent Yorgey. 2012. |
||
+ | |||
+ | ;[http://wwwhome.ewi.utwente.nl/~fokkinga/mmf2005d-houghtrf-JFPpre.pdf 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://www.iai.uni-bonn.de/~jv/icfp10.pdf Combining Syntactic and Semantic Bidirectionalization] |
||
+ | :Janis Voigtländer, Zhenjiang Hu, Kazutaka Matsuda, Meng Wang. 2010. |
||
+ | |||
+ | ;[http://wwwtcs.inf.tu-dresden.de/~voigt/icfp09.pdf 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://wwwtcs.inf.tu-dresden.de/~voigt/popl09-2.pdf Bidirectionalization for Free!] |
||
+ | :Janis Voigtländer. 2009. |
||
+ | |||
+ | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP08.pdf Functional Pearl: Streams and Unique Fixed Points] |
||
+ | :Ralf Hinze, ICFP 2008 |
||
+ | |||
+ | ;[ftp://ftp.diku.dk/diku/semantics/papers/D-582.pdf Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time] |
||
+ | :Fritz Henglein. 2008 |
||
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl202-voigtlaender.pdf Much Ado about Two: A Pearl on Parallel Prefix Computation] |
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl202-voigtlaender.pdf Much Ado about Two: A Pearl on Parallel Prefix Computation] |
||
− | :Janis Voigtländer. 2008 |
+ | :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] |
;[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. |
: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]. |
||
+ | |||
⚫ | |||
:James McKinna and Joel Wright. 2006. |
:James McKinna and Joel Wright. 2006. |
||
Line 38: | Line 87: | ||
:Conor McBride and Ross Paterson. 2006. |
:Conor McBride and Ross Paterson. 2006. |
||
− | ;[http://web.comlab.ox.ac.uk/ |
+ | ;[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/comp150fp/archive/richard-bird/sudoku.pdf A program to solve Sudoku] |
||
⚫ | |||
;[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] |
||
Line 64: | Line 116: | ||
;[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] |
||
⚫ | |||
;[http://pauillac.inria.fr/~maranget/enum/pearl.ps Functional satisfaction] |
;[http://pauillac.inria.fr/~maranget/enum/pearl.ps Functional satisfaction] |
||
Line 71: | Line 126: | ||
: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.rutgers.edu/~ccshan/prepose/p1214-kiselyov.pdf also here]) |
||
− | ;[http:// |
+ | ;[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 78: | Line 133: | ||
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform] |
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform] |
||
− | :Richard Bird and Shin-Cheng Mu. 2004. ([http://web.comlab.ox.ac.uk/ |
+ | :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/ |
+ | ;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases] |
:Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004. |
:Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004. |
||
Line 95: | Line 150: | ||
:Andrew J. Kennedy. 2004. |
:Andrew J. Kennedy. 2004. |
||
− | ;[ |
+ | ;[www.cse.chalmers.se/edu/course/afp/Papers/parser-claessen.pdf Parallel Parsing Processes] |
:Koen Claessen. 2004. |
:Koen Claessen. 2004. |
||
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/1.pdf Derivation of a logarithmic time carry lookahead addition circuit] |
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/1.pdf 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://journals.cambridge.org |
+ | :John O'Donnell and Gudula Runger. 2004. ([http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=1030343 ACM]) ([http://journals.cambridge.org/action/displayAbstract?aid=254717 JFP]) ([http://www.informatik.uni-bonn.de/~ralf/hw2001/1.html Homepage]). |
+ | |||
⚫ | |||
⚫ | |||
;[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 |
+ | :Jean-Christophe Filliatre and Francois Pottier. 2003. |
− | ;[http://www. |
+ | ;[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. |
+ | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/Format.ps.gz Formatting: a class act] |
:Ralf Hinze. 2003. |
:Ralf Hinze. 2003. |
||
− | ;[http://www. |
+ | ;[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 119: | Line 177: | ||
:Bryan Ford. 2002. |
:Bryan Ford. 2002. |
||
− | ;[http:// |
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing] |
:Magnus Carlsson. 2002. |
: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://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms] |
;[http://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms] |
||
Line 128: | Line 190: | ||
:Richard Bird. 2001. |
:Richard Bird. 2001. |
||
− | ;[http://www. |
+ | ;[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 137: | Line 199: | ||
:Daniel Fridlender and Mia Indrika. 2001. |
:Daniel Fridlender and Mia Indrika. 2001. |
||
− | ;[http://www. |
+ | ;[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 146: | Line 208: | ||
:Chris Okasaki. 2000. |
:Chris Okasaki. 2000. |
||
− | ;[http://www. |
+ | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers] |
:Ralf Hinze. 2000. |
:Ralf Hinze. 2000. |
||
Line 155: | Line 217: | ||
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000. |
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000. |
||
− | ;[http:// |
+ | ;[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. |
+ | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/BinomialHeaps/index.html Explaining binomial heaps] |
:Ralf Hinze. 1999. |
:Ralf Hinze. 1999. |
||
Line 170: | Line 232: | ||
: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/ |
+ | ;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/radix.ps.gz A pointless derivation of radix sort] |
:Jeremy Gibbons. 1999. |
:Jeremy Gibbons. 1999. |
||
Line 176: | Line 238: | ||
:Graham Hutton and Erik Meijer . 1998. |
:Graham Hutton and Erik Meijer . 1998. |
||
− | ;[http:// |
+ | ;[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 182: | Line 244: | ||
:Martin Erwig. 1998. |
:Martin Erwig. 1998. |
||
− | ;[http:// |
+ | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1673 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- |
+ | ;[http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper] |
:Gerard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]). |
:Gerard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]). |
||
− | ;[http:// |
+ | ;[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. |
||
Line 194: | Line 256: | ||
:Chris Okasaki. 1997. |
:Chris Okasaki. 1997. |
||
− | ;[http://web.comlab.ox.ac.uk/ |
+ | ;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem] |
:Jeremy Gibbons. 1996. |
:Jeremy Gibbons. 1996. |
||
Line 201: | Line 263: | ||
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees] |
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees] |
||
− | : |
+ | :Andrew J. Kennedy. 1996. |
+ | ;[http://research.microsoft.com/~nick/newtrans.pdf Undoing Dynamic Typing] |
||
⚫ | |||
+ | :Nick Benton. 2008. |
||
+ | |||
⚫ | |||
: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:// |
+ | ;[http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act] |
− | :Stephen Adams. 1993. ([http://haskell.org/ |
+ | :Stephen Adams. 1993. ([http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html Data.Set]). |
=== Potential Pearls === |
=== Potential Pearls === |
||
Line 213: | Line 278: | ||
Unpublished pearls. |
Unpublished pearls. |
||
− | ;[http://www. |
+ | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/Quote.pdf Typed Quote/AntiQuote] |
:Ralf Hinze. Unpublished work in progress. |
:Ralf Hinze. Unpublished work in progress. |
||
+ | |||
+ | ;[http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf α-conversion is easy] |
||
+ | :Thorsten Altenkirch. Unpublished draft. |
||
=== Offline === |
=== Offline === |
||
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section! |
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_S0956796804005210 Calculating the Sieve of Eratosthenes] |
||
⚫ | |||
;[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/ |
+ | :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 |
;On generating unique names |
||
Line 238: | Line 300: | ||
:Richard Bird and Sharon Curtis. 2006. ([http://cms.brookes.ac.uk/staff/SharonCurtis/publications/index.html#celebrities See also]). |
:Richard Bird and Sharon Curtis. 2006. ([http://cms.brookes.ac.uk/staff/SharonCurtis/publications/index.html#celebrities See also]). |
||
− | ;[http://journals.cambridge.org |
+ | ;[http://journals.cambridge.org/action/displayAbstract?aid=254705 On tiling a chessboard] |
⚫ | |||
− | |||
− | ;[http://www.journals.cambridge.org/action/displayAbstract?fromPage=online&aid=254705 On tiling a chessboard] |
||
:Richard Bird. 2004. ([http://portal.acm.org/citation.cfm?id=1030333.1030336 ACM]) |
:Richard Bird. 2004. ([http://portal.acm.org/citation.cfm?id=1030333.1030336 ACM]) |
||
− | ;[http://journals.cambridge.org |
+ | ;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44141 Meertens number] |
:Richard Bird. 1998. |
:Richard Bird. 1998. |
||
− | ;[http://journals.cambridge.org |
+ | ;[http://journals.cambridge.org/action/displayAbstract?aid=44091 On merging and selection] |
− | :Richard Bird. 1997. (See also [http://web.comlab.ox.ac.uk/ |
+ | :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/ |
+ | ;[http://journals.cambridge.org/action/displayAbstract?aid=44107 On building trees with minimum height] |
− | :Richard Bird. 1997. ([http://web.comlab.ox.ac.uk/ |
+ | :Richard Bird. 1997. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird97:OnBuilding Bib]). |
;The Last Tail. |
;The Last Tail. |
||
− | :Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/ |
+ | :Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird93:Last Bib]). |
;Two Greedy Algorithms |
;Two Greedy Algorithms |
Revision as of 08:50, 25 August 2013
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.
- 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 Pretty-Printing
- 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 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. (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).
- 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.
- [www.cse.chalmers.se/edu/course/afp/Papers/parser-claessen.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 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.
- 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!
- 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).
- 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).