Difference between revisions of "Research papers/Functional pearls"
Jump to navigation
Jump to search
m (Replace dead links with web archive version) |
Noughtmare (talk | contribs) (Add grokking the sequent calculus pearl) |
||
(14 intermediate revisions by 7 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] |
+ | 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 == |
||
The history of functional pearls is covered by: |
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. |
+ | *: 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] |
|
− | :Richard Bird. ICFP 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] |
|
− | :Mike Spivey |
+ | *: 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 |
+ | *: Olivier Danvy and Michael Spivey. July 2007 |
− | There have been many functional pearls in JFP |
+ | 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 |
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]. |
[https://www.cs.ox.ac.uk/publications/publication2338-abstract.html The Fun of Programming]. |
||
Line 27: | Line 29: | ||
Some advice on writing pearls for JFP is available in this [http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/ editorial]. |
Some advice on writing pearls for JFP is available in this [http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/ editorial]. |
||
− | + | == Online == |
|
− | Functional pearls online |
+ | Functional pearls available online. |
+ | ;2024 |
||
− | ;[http://www.cs.ox.ac.uk/jeremy.gibbons/publications/proyo.pdf What You Needa Know about Yoneda: Profunctor Optics and the Yoneda Lemma] |
||
+ | * [https://arxiv.org/abs/2406.14719 Grokking the Sequent Calculus (pre-print)] David Binder, Marco Tzschentke, Marius Müller, Klaus Ostermann. |
||
− | :Guillaume Boisseau, Jeremy Gibbons. 2018. |
||
+ | ;2023 |
||
− | ;[https://jyp.github.io/pdf/Prettiest.pdf A Pretty But Not Greedy Printer] |
||
+ | * [https://doi.org/10.1145/3607853 More Fixpoints!] - Joachim Breitner. |
||
− | :Jean-Philippe Bernardy. 2017. |
||
+ | * [https://doi.org/10.1145/3607849 HasChor: Functional Choreographic Programming for All] - Gan Shen, Shun Kashiwa, Lindsey Kuper. |
||
+ | ;2022 |
||
− | ;[https://eprint.ncl.ac.uk/file_store/production/239461/EF82F5FE-66E3-4F64-A1AC-A366D1961738.pdf Algebraic Graphs with Class] |
||
+ | * [https://doi.org/10.1145/3547640 'do' Unchained: Embracing Local Imperativity in a Purely Functional Language] - Sebastian Ullrich, Leonardo de Moura. |
||
− | :Andrey Mokhov. 2017. |
||
+ | * [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 |
||
− | ;[https://www.cis.upenn.edu/~llamp/pdf/urns.pdf Ode on a Random Urn] |
||
+ | * [https://www.cs.nott.ac.uk/~pszgmh/123.pdf It’s Easy As 1,2,3] - Graham Hutton. |
||
− | :Leonidas Lampropoulos, Antal Spector-Zabusky, Kenneth Foner. 2017. |
||
+ | * [https://doi.org/10.1145/3471874.3472984 Design Patterns for Parser Combinators] - Jamie Willis, Nicolas Wu. |
||
+ | ;2020 |
||
− | ;[http://homes.sice.indiana.edu/ccshan/rational/pearl.pdf Deriving a Probability Density Calculator] |
||
+ | * [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. |
||
− | :Wazim Mohammed Ismail, Chung-chieh Shan. 2016. |
||
+ | * [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.iis.sinica.edu.tw/~scm/pub/queueing-glueing.pdf Queueing and Glueing for Optimal Partitioning] |
||
+ | * [https://jyp.github.io/pdf/Prettiest.pdf A Pretty But Not Greedy Printer] - Jean-Philippe Bernardy. |
||
− | :Shin-Cheng Mu, Yu-Hsi Chiang, Yu-Han Lyu. 2016. |
||
+ | * [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://www.cs.ox.ac.uk/jeremy.gibbons/publications/delivery.pdf Free Delivery] |
||
+ | * [http://homes.sice.indiana.edu/ccshan/rational/pearl.pdf Deriving a Probability Density Calculator] - Wazim Mohammed Ismail and Chung-chieh Shan. |
||
− | :Jeremy Gibbons. 2016. |
||
+ | * [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 |
||
− | ;[https://www.informatik.uni-kiel.de//~sad/icfp2016-preprint.pdf All Sorts of Permutations] |
||
+ | * [https://www.fceia.unr.edu.ar/~mauro/pubs/smartviews/smartviews.pdf A Smart View on Datatypes] - Mauro Jaskelioff and Exequiel Rivas. |
||
− | :Jan Christiansen, Nikita Danilenko, Sandra Dylus. 2016. |
||
+ | * [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. |
||
− | ;[https://www.fceia.unr.edu.ar/~mauro/pubs/smartviews/smartviews.pdf A Smart View on Datatypes] |
||
+ | * [http://web.cecs.pdx.edu/~mpj/snakecube/ Solving the Snake Cube Puzzle in Haskell] - Mark P. Jones. |
||
− | :Mauro Jaskelioff, Exequiel Rivas. 2015. |
||
+ | ;2012 |
||
− | ;[http://www.cse.chalmers.se/~russo/publications_files/pearl-russo.pdf Two Can Keep a Secret, If One of Them Uses Haskell] |
||
+ | * [http://www.cs.tufts.edu/~nr/cs257/archive/mike-spivey/maybe-not-enough.pdf When Maybe is not good enough] - Michael Spivey. |
||
− | :Alejandro Russo. 2015. |
||
+ | * [http://ozark.hendrix.edu/~yorgey/pub/monoid-pearl.pdf Monoids: Theme and Variations] - Brent Yorgey. |
||
+ | ;2011 |
||
− | ;[http://web.cecs.pdx.edu/~mpj/snakecube/ Solving the Snake Cube Puzzle in Haskell] |
||
+ | * [http://dx.doi.org/10.1017/S0956796810000341 The Hough transform] - Maarten Fokkinga. |
||
− | :Mark P. Jones. 2013. |
||
+ | * [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.tufts.edu/~nr/cs257/archive/mike-spivey/maybe-not-enough.pdf When Maybe is not good enough] |
||
+ | * [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/pearl.pdf Every Bit Counts] - Dimitrios Vytiniotis and Andrew Kennedy. |
||
− | :Michael Spivey. 2012. |
||
+ | * [http://sebfisch.github.io/haskell-regexp/regexp-play.pdf A Play on Regular Expressions] - Sebastian Fischer. Frank Huch and Thomas Wilke. |
||
+ | ;2009 |
||
− | ;[http://ozark.hendrix.edu/~yorgey/pub/monoid-pearl.pdf Monoids: Theme and Variations] |
||
+ | * [http://dx.doi.org/10.1145/1596550.1596577 Free Theorems Involving Type Constructor Classes] - Janis Voigtländer. |
||
− | :Brent Yorgey. 2012. |
||
+ | * [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://dx.doi.org/10.1017/S0956796810000341 The Hough transform] |
||
+ | * [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. |
||
− | :Maarten Fokkinga. 2011. |
||
+ | * [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.staff.science.uu.nl/~swier004/publications/2011-jfp.pdf Sorted. Verifying the Problem of the Dutch National Flag in Agda] |
||
+ | * [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. |
||
− | :Wouter Swierstra. 2011. |
||
+ | * [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.ox.ac.uk/people/ralf.hinze/publications/Quote.pdf Typed Quote/Antiquote - Or: Compile-time Parsing] |
||
+ | * [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. |
||
− | :Ralf Hinze. 2011. |
||
+ | * [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://research.microsoft.com/en-us/people/dimitris/every-bit-counts.pdf Every Bit Counts] |
||
+ | * [http://dx.doi.org/10.1017/S095679680300474X Marble mingling] - Sharon Curtis. |
||
− | :Dimitrios Vytiniotis, Andrew Kennedy. 2010. |
||
+ | * [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://sebfisch.github.io/haskell-regexp/regexp-play.pdf A Play on Regular Expressions] |
||
+ | * [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. |
||
− | :Sebastian Fischer. Frank Huch, Thomas Wilke. 2010. |
||
+ | * [http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate] - James Cheney. |
||
+ | ;2004 |
||
− | ;[http://dx.doi.org/10.1145/1596550.1596577 Free Theorems Involving Type Constructor Classes] |
||
+ | * [http://dx.doi.org/10.1017/S0956796804005209 Pickler Combinators] - Andrew Kennedy. |
||
− | :Janis Voigtländer. 2009. |
||
+ | * [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.cs.kent.ac.uk/pubs/2009/2847/content.pdf Linear, Bounded, Functional Pretty-Printing] |
||
− | :S. Doaitse Swierstra, Olaf Chitil. 2009. |
||
+ | * [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://dx.doi.org/10.1145/1480881.1480904 Bidirectionalization for Free!] |
||
+ | * [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global variables in Haskell] - John Hughes. |
||
− | :Janis Voigtländer. 2009. |
||
+ | * [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://web.engr.oregonstate.edu/~walkiner/papers/jfp09-hagl.pdf A Domain-Specific Language for Experimental Game Theory] |
||
+ | * [http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices] - Sergio Antoy and Michael Hanus. |
||
− | :Eric Walkingshaw and Martin Erwig. 2009. |
||
+ | * [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 |
||
− | ;[https://web.archive.org/web/20160527131614/https://www.staff.science.uu.nl/~swier004/Publications/DataTypesALaCarte.pdf Functional Pearl: Data Types A La Carte] |
||
+ | * [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. |
||
− | :Wouter Swierstra, 2008 |
||
+ | * [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://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP08.pdf Functional Pearl: Streams and Unique Fixed Points] |
||
+ | * [http://www.cs.ox.ac.uk/ralf.hinze/publications/SearchTree.ps.gz A fresh look at binary search trees] - Ralf Hinze. |
||
− | :Ralf Hinze, ICFP 2008 |
||
+ | * [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://dx.doi.org/10.1145/1411204.1411220 Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time] |
||
+ | * [http://www.cs.nott.ac.uk/~gmh/wgp01/hinze-paper.pdf Haskell does it with class: Functorial unparsing] - Ralf Hinze. |
||
− | :Fritz Henglein. 2008 |
||
+ | * [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://dx.doi.org/10.1145/1328438.1328445 Much Ado about Two: A Pearl on Parallel Prefix Computation] |
||
+ | * [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. |
||
− | :Janis Voigtländer. 2008. |
||
+ | * [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://strictlypositive.org/CJ.pdf Clowns to the Left of me, Jokers to the Right: Dissecting Data Structures]: Conor McBride. 2008. |
||
+ | * [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039 A poor man's concurrency monad] - Koen Claessen. |
||
+ | * [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://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. |
||
+ | ;1998 |
||
− | ;[https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2007.pdf Scrap Your Zippers] |
||
+ | * [http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell] - Graham Hutton and Erik Meijer. |
||
− | :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.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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.4086 A type-correct, stack-safe, provably correct expression compiler in Epigram] |
||
+ | * [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] |
||
− | :James McKinna and Joel Wright. 2006. |
||
+ | *: 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.soi.city.ac.uk/~ross/papers/Applicative.pdf Applicative Programming with Effects] |
||
+ | * [http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper] |
||
− | :Conor McBride and Ross Paterson. 2006. |
||
+ | *: 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://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/rationals.pdf Enumerating the rationals] |
||
+ | * [https://web.archive.org/web/20120314024849/http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees] - Chris Okasaki. |
||
− | :Jeremy Gibbons, David Lester and Richard Bird. 2006. |
||
+ | ;1996 |
||
− | ;[http://www.cs.tufts.edu/~nr/cs257/archive/richard-bird/sudoku.pdf A program to solve Sudoku] |
||
+ | * [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem] - Jeremy Gibbons. |
||
− | :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://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/PFP_JFP06.pdf Probabilistic functional programming in Haskell] |
||
+ | * [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 and Steve Kollmansberger. 2006. |
||
+ | ;1993 |
||
− | ;[http://dx.doi.org/10.1017/S095679680300474X Marble mingling] |
||
+ | * [http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act] |
||
− | :Sharon Curtis. 2006. |
||
+ | *: 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://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Strong Types for Relational Databases] |
||
− | :Alexandra Silva, Joost Visser. 2006. (Haskell Workshop) |
||
+ | ;1992 |
||
− | ;[http://okmij.org/ftp/papers/LogicT.pdf Backtracking, interleaving, and terminating monad transformers] |
||
+ | * [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] |
||
− | :Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005. |
||
+ | *: 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://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate] |
||
− | :James Cheney. 2005. |
||
+ | ;1991 |
||
− | ;[http://dx.doi.org/10.1017/S0956796804005209 Pickler Combinators] |
||
+ | * [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. |
||
− | :Andrew Kennedy. 2004. |
||
+ | ;1988 |
||
− | ;[http://web.cecs.pdx.edu/~mpj/pubs/composing-fractals.pdf Composing fractals] |
||
+ | * [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages] - F. Warren Burton. |
||
− | :Mark P. Jones. 2004. |
||
+ | == Potential pearls == |
||
− | ;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages] |
||
− | :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] |
||
− | :Oleg Kiselyov, Chung-chieh Shan. 2004. |
||
− | |||
− | ;[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]) |
||
− | |||
− | ;[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, James McKinna. 2004. |
||
− | |||
− | ;[http://dx.doi.org/10.1017/S0956796804005118 Inverting the Burrows Wheeler transform] |
||
− | :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/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases] |
||
− | :Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004. |
||
− | |||
− | ;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices] |
||
− | :Sergio Antoy and Michael Hanus. 2004. |
||
− | |||
− | ;[http://dx.doi.org/10.1017/S0956796804005106 Functional chart parsing of context-free grammars] |
||
− | :Peter Ljunglf. 2004. |
||
− | |||
− | ;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast] |
||
− | :Stephanie Weirich. 2004. |
||
− | |||
− | ;[http://www.cse.chalmers.se/edu/course/afp/Papers/parser-claessen.pdf Parallel Parsing Processes] |
||
− | :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] |
||
− | :Jean-Christophe Filliatre and Francois Pottier. 2003. |
||
− | |||
− | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/HW03.pdf Trouble shared is trouble halved] |
||
− | :Richard Bird, Ralf Hinze. 2003 |
||
− | |||
− | ;[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. |
||
− | |||
− | ;[http://www.cs.nott.ac.uk/~gmh/countdown.pdf The countdown problem] |
||
− | :Graham Hutton. 2002. |
||
− | |||
− | ;[http://pdos.csail.mit.edu/papers/packrat-parsing:icfp02.pdf Packrat parsing: simple, powerful, lazy, linear time, functional pearl] |
||
− | :Bryan Ford. 2002. |
||
− | |||
− | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing] |
||
− | :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. |
||
− | |||
− | ;[http://dx.doi.org/10.1017/S0956796801004038 Maximum marking problems] |
||
− | :Richard Bird. 2001. |
||
− | |||
− | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/TheWeb.ps.gz Weaving a web] |
||
− | :Ralf Hinze and Johan Jeuring. 2001. |
||
− | |||
− | ;[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. 2001. |
||
− | |||
− | ;[http://www.brics.dk/RS/01/10/BRICS-RS-01-10.ps.gz Do we need dependent types?] |
||
− | :Daniel Fridlender and Mia Indrika. 2001. |
||
− | |||
− | ;[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. |
||
− | |||
− | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.2420 Combinators for breadth-first search] |
||
− | :Michael Spivey. 2000 |
||
− | |||
− | ;[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. 2000. |
||
− | |||
− | ;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers] |
||
− | :Ralf Hinze. 2000. |
||
− | |||
− | ;[http://www.cis.upenn.edu/~bcpierce/papers/rsr.ps Recursive subtyping revealed] |
||
− | :Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. 2000. |
||
− | |||
− | ;[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. |
||
− | |||
− | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8039 A poor man's concurrency monad] |
||
− | :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] |
||
− | :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] |
||
− | :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] |
||
− | :Graham Hutton and Erik Meijer . 1998. |
||
− | |||
− | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6891 Polytypic unification] |
||
− | :Patrik Jansson and Johan Jeuring. 1998. |
||
− | |||
− | ;[http://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf Diets for fat sets] |
||
− | :Martin Erwig. 1998. |
||
− | |||
− | ;[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. |
||
− | |||
− | ;[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]). |
||
− | |||
− | ;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096 Lazy wheel sieves and spirals of primes] |
||
− | :Colin Runciman. 1997. |
||
− | |||
− | ;[https://web.archive.org/web/20120314024849/http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees] |
||
− | :Chris Okasaki. 1997. |
||
− | |||
− | ;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem] |
||
− | :Jeremy Gibbons. 1996. |
||
− | |||
− | ;[http://www.cs.nott.ac.uk/~gmh/basics.pdf Back to Basics: Deriving Representation Changers Functionally]. |
||
− | :Graham Hutton, Erik Meijer. 1996. |
||
− | |||
− | ;[http://dx.doi.org/10.1017/S0956796800001830 Drawing Trees] |
||
− | :Andrew J. Kennedy. 1996. |
||
− | |||
− | ;[http://research.microsoft.com/~nick/newtrans.pdf Undoing Dynamic Typing] |
||
− | :Nick Benton. 2008. |
||
− | |||
− | ;[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]). |
||
− | |||
− | ;[http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act] |
||
− | :Stephen Adams. 1993. ([http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html Data.Set]). |
||
− | |||
− | === Potential Pearls === |
||
Unpublished pearls. |
Unpublished pearls. |
||
− | + | * [http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf α-conversion is easy] |
|
− | :Thorsten Altenkirch. |
+ | *: 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! |
||
− | |||
− | ;[http://www.cs.kent.ac.uk/pubs/2001/1293/index.html Red-black trees with types] |
||
− | :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 |
||
− | :Lennart Augustsson, M Rittri, D Synek. 1994. ([http://www.cs.chalmers.se/~rittri/#publications Rittri's homepage]) |
||
− | |||
− | ;A Symmetric Set of Efficient List Operations. |
||
− | :Rob R. Hoogerwoord, 1992. ([https://venus.tue.nl/ep-cgi/ep_publ.opl?taal=NL&fac_id=92&rn=19840694 Hoogerwoord's homepage]). |
||
− | |||
− | ;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming] |
||
− | :Richard Bird and Sharon Curtis. 2006. |
||
− | |||
− | ;[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. |
||
− | |||
− | ;[http://journals.cambridge.org/action/displayAbstract?aid=44091 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/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]). |
||
− | |||
− | ;The Last Tail. |
||
− | :Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird93:Last Bib]). |
||
+ | <!-- |
||
− | ;Two Greedy Algorithms |
||
+ | == Offline == |
||
− | :Richard Bird, 1992. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#Bird92:Two Bib]). |
||
+ | These appear not to be available online, unfortunately. If you know where they live, please link and and move into the 'online' section! |
||
− | ;On Removing Duplicates |
||
+ | --> |
||
− | :Richard Bird. 1991. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#DBLP:journals/jfp/Bird91a Bib]). |
||
[[Category:Research]] [[Category:Tutorials]] |
[[Category:Research]] [[Category:Tutorials]] |
Latest revision as of 15:21, 12 July 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:
- How to Write a Functional Pearl
- Richard Bird. ICFP 2006.
- Fifteen years of functional pearls
- Richard Bird. ICFP 2006.
- Strachey's functional pearl and 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 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.
- 2024
- Grokking the Sequent Calculus (pre-print) David Binder, Marco Tzschentke, Marius Müller, Klaus Ostermann.
- 2023
- More Fixpoints! - Joachim Breitner.
- HasChor: Functional Choreographic Programming for All - Gan Shen, Shun Kashiwa, Lindsey Kuper.
- 2022
- 'do' Unchained: Embracing Local Imperativity in a Purely Functional Language - Sebastian Ullrich, Leonardo de Moura.
- Monadic Compiler Calculation - Patrick Bahr, Graham Hutton.
- Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structured Control Flow - Norman Ramsey.
- 2021
- It’s Easy As 1,2,3 - Graham Hutton.
- Design Patterns for Parser Combinators - Jamie Willis, Nicolas Wu.
- 2020
- Achieving high-performance the functional way - Bastian Hagedorn, Johannes Lenfers, Thomas Kœhler, Xueying Qin, Sergei Gorlatch, Michel Steuwer.
- Parsing with zippers - Pierce Darragh, Michael D. Adams
- Separation Logic for Sequential Programs - Arthur Charguéraud
- Strong Functional Pearl: Harper's Regular-Expression Matcher in Cedille - Aaron Stump, Chris Jenkins, Stephan Spahn, Colin McDonald
- The simple essence of algebraic subtyping: principal type inference with subtyping made easy - Lionel Parreaux
- A Graded Monad for Deadlock-Free Concurrency - Andrej Ivašković, Alan Mycroft
- Finger Trees explained anew, and slightly simplified - Koen Claessen.
- Stitch: The Sound Type-Indexed Type Checker - Richard A. Eisenberg
- 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
- What You Needa Know about Yoneda: Profunctor Optics and the Yoneda Lemma - Guillaume Boisseau and Jeremy Gibbons.
- 2017
- A Pretty But Not Greedy Printer - Jean-Philippe Bernardy.
- Algebraic Graphs with Class - Andrey Mokhov.
- Ode on a Random Urn - Leonidas Lampropoulos, Antal Spector-Zabusky and Kenneth Foner.
- 2016
- Deriving a Probability Density Calculator - Wazim Mohammed Ismail and Chung-chieh Shan.
- Queueing and Glueing for Optimal Partitioning - Shin-Cheng Mu, Yu-Hsi Chiang and Yu-Han Lyu.
- Free Delivery - Jeremy Gibbons.
- All Sorts of Permutations - Jan Christiansen, Nikita Danilenko and Sandra Dylus.
- 2015
- A Smart View on Datatypes - Mauro Jaskelioff and Exequiel Rivas.
- Two Can Keep a Secret and If One of Them Uses Haskell - Alejandro Russo.
- 2013.
- Solving the Snake Cube Puzzle in Haskell - Mark P. Jones.
- 2012
- When Maybe is not good enough - Michael Spivey.
- Monoids: Theme and Variations - Brent Yorgey.
- 2011
- The Hough transform - Maarten Fokkinga.
- Sorted. Verifying the Problem of the Dutch National Flag in Agda - Wouter Swierstra.
- Typed Quote/Antiquote - Or: Compile-time Parsing - Ralf Hinze.
- 2010
- Every Bit Counts - Dimitrios Vytiniotis and Andrew Kennedy.
- A Play on Regular Expressions - Sebastian Fischer. Frank Huch and Thomas Wilke.
- 2009
- Free Theorems Involving Type Constructor Classes - Janis Voigtländer.
- Linear, Bounded and Functional Pretty-Printing - S. Doaitse Swierstra and Olaf Chitil.
- Bidirectionalization for Free! - Janis Voigtländer.
- A Domain-Specific Language for Experimental Game Theory - Eric Walkingshaw and Martin Erwig.
- 2008
- Functional Pearl: Data Types A La Carte - Wouter Swierstra.
- Functional Pearl: Streams and Unique Fixed Points - Ralf Hinze.
- Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time - Fritz Henglein.
- Undoing Dynamic Typing - Nick Benton.
- Much Ado about Two: A Pearl on Parallel Prefix Computation - Janis Voigtländer.
- Clowns to the Left of me and Jokers to the Right: Dissecting Data Structures: Conor McBride.
- 2007
- Functional Pearl: The Great Escape: Or how to jump the border without getting caught - David Herman.
- Scrap Your Zippers
- Michael Adams. (superseded by the WGP 2010 version.)
- 2006
- A type-correct, stack-safe and provably correct expression compiler in Epigram - James McKinna and Joel Wright.
- Applicative Programming with Effects - Conor McBride and Ross Paterson.
- Enumerating the rationals - Jeremy Gibbons, David Lester and Richard Bird.
- A program to solve Sudoku
- Richard Bird. (slides; an implementation in Literate Haskell by Graham Hutton.)
- Probabilistic functional programming in Haskell - Martin Erwig and Steve Kollmansberger.
- Marble mingling - Sharon Curtis.
- Strong Types for Relational Databases - Alexandra Silva and Joost Visser.
- Finding celebrities: A lesson in functional programming - Richard Bird and Sharon Curtis.
- 2005
- Backtracking, interleaving and and terminating monad transformers - Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry.
- Scrap your Nameplate - James Cheney.
- 2004
- Pickler Combinators - Andrew Kennedy.
- Composing fractals - Mark P. Jones.
- Enumerating the strings of regular languages - M. Douglas McIlroy.
- Calculating the Sieve of Eratosthenes - Lambert Meertens. (slides.)
- Functional satisfaction - Luc Maranget. (more info.)
- Implicit configurations--or and type classes reflect the values of types - Oleg Kiselyov and Chung-chieh Shan.
- Global variables in Haskell - John Hughes.
- I am not a number -- I am a free variable - Conor McBride and James McKinna.
- Inverting the Burrows Wheeler transform - Richard Bird and Shin-Cheng Mu. (also here.)
- Parsing permutation phrases - Arthur Baars and Andres Loh and S. Doaitse Swierstra.
- Concurrent distinct choices - Sergio Antoy and Michael Hanus.
- Functional chart parsing of context-free grammars - Peter Ljunglf.
- Type-Safe Cast - Stephanie Weirich.
- Parallel Parsing Processes - Koen Claessen.
- Derivation of a logarithmic time carry lookahead addition circuit - John O'Donnell and Gudula Runger.
- Linear lambda calculus and PTIME-completeness - Harry G. Mairson.
- On tiling a chessboard - Richard Bird.
- 2003
- Producing all ideals of a forest and functionally - Jean-Christophe Filliatre and Francois Pottier.
- Trouble shared is trouble halved - Richard Bird and Ralf Hinze.
- Formatting: a class act - Ralf Hinze.
- 2002
- A fresh look at binary search trees - Ralf Hinze.
- The countdown problem - Graham Hutton.
- Packrat parsing: simple, powerful, lazy, linear time and functional pearl - Bryan Ford.
- Monads for Incremental Computing - Magnus Carlsson.
- 2001
- Haskell does it with class: Functorial unparsing - Ralf Hinze.
- Unfolding pointer algorithms - Richard Bird.
- Maximum marking problems - Richard Bird.
- Weaving a web - Ralf Hinze and Johan Jeuring.
- Normalization by evaluation with typed abstract syntax - Olivier Danvy, Morten Rhiger and Kristoffer H. Rose.
- Do we need dependent types? - Daniel Fridlender and Mia Indrika.
- Red-black trees with types - Stefan Kahrs. (code.)
- 2000
- Perfect trees and bit-reversal permutations and a revision of Technical Report IAI-TR-99-4 - Ralf Hinze.
- Combinators for breadth-first search - Michael Spivey.
- Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design - Chris Okasaki.
- Deriving Backtracking Monad Transformers - Ralf Hinze.
- Recursive subtyping revealed - Vladimir Gapeyev, Michael Y. Levin and Benjamin C. Pierce.
- Composing contracts: an adventure in financial engineering - Simon Peyton Jones, Jean-Marc Eber and Julian Seward.
- 1999
- A poor man's concurrency monad - Koen Claessen.
- Explaining binomial heaps - Ralf Hinze.
- Power series and power serious - M. Douglas McIlroy.
- Red-black trees in a functional setting - Chris Okasaki.
- Proof-directed debugging
- Robert Harper. (see also Proof-directed debugging: revisited for a first-order version.)
- A pointless derivation of radix sort - Jeremy Gibbons.
- 1998
- Monadic parsing in Haskell - Graham Hutton and Erik Meijer.
- Polytypic unification - Patrik Jansson and Johan Jeuring.
- Diets for fat sets - Martin Erwig.
- Even higher-order functions for parsing or Why would anyone ever want to use a sixth-order function? - Chris Okasaki.
- Meertens number - Richard Bird.
- 1997
- On merging and selection
- Richard Bird. (see also More on Merging and Selection.)
- On building trees with minimum height - Richard Bird.
- The Zipper
- Gerard Huet. (see also The Haskell Wikibook).
- Lazy wheel sieves and spirals of primes - Colin Runciman.
- Three algorithms on Braun trees - Chris Okasaki.
- 1996
- The Third Homomorphism Theorem - Jeremy Gibbons.
- Back to Basics: Deriving Representation Changers Functionally - Graham Hutton and Erik Meijer.
- Drawing Trees - Andrew J. Kennedy.
- Deriving Tidy Drawings of Trees
- Jeremy Gibbons. (see also the research report.)
- 1994
- On generating unique names - Lennart Augustsson, Mikael Rittri and Dan Synek.
- 1993
- Efficient Sets - A Balancing Act
- Stephen Adams. (
Data.Set
code.)
- Stephen Adams. (
- The Last Tail - Richard Bird.
- 1992
- A Symmetric Set of Efficient List Operations
- Rob R. Hoogerwoord. (Hoogerwoord's homepage.)
- Two Greedy Algorithms - Richard Bird.
- 1991
- On Removing Duplicates - Richard Bird.
- 1988
- Nondeterminism with Referential Transparency in Functional Programming Languages - F. Warren Burton.
Potential pearls
Unpublished pearls.
- α-conversion is easy
- Thorsten Altenkirch. (unpublished draft.)