https://wiki.haskell.org/api.php?action=feedcontributions&user=Jeremygibbons&feedformat=atomHaskellWiki - User contributions [en]2021-12-07T07:10:16ZUser contributionsMediaWiki 1.27.4https://wiki.haskell.org/index.php?title=Research_papers/Functional_pearls&diff=42083Research papers/Functional pearls2011-09-15T02:34:32Z<p>Jeremygibbons: </p>
<hr />
<div>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.<br />
<br />
The history of functional pearls is covered by:<br />
<br />
;[http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]<br />
:Richard Bird. ICFP 2006.<br />
<br />
;[http://portal.acm.org/ft_gateway.cfm?id=1159832&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Fifteen years of functional pearls]<br />
:Richard Bird. ICFP 2006.<br />
<br />
;[http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl, forty years on]<br />
:Mike Spivey, 2006.<br />
<br />
;[http://www.brics.dk/RS/07/14/index.html On Barron and Strachey's Cartesian Product Function]<br />
: Olivier Danvy and Michael Spivey, July 2007<br />
<br />
There have been many functional pearls in JFP, and some others at<br />
ICFP and the Haskell Workshop. There is also a collection of them in<br />
[http://web2.comlab.ox.ac.uk/oucl/publications/books/fop/ The Fun of Programming].<br />
<br />
The pearls tend to concentrate on:<br />
<br />
* Examples of program calculation and proof<br />
* Neat presentations of new or old data structures<br />
* Interesting applications and techniques<br />
<br />
Some advice on writing pearls for JFP is available in this [http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/ editorial].<br />
<br />
=== Online ===<br />
<br />
Functional pearls online:<br />
<br />
;[http://research.microsoft.com/en-us/people/dimitris/every-bit-counts.pdf Every Bit Counts]<br />
:Dimitrios Vytiniotis, Andrew Kennedy. 2010.<br />
<br />
;[http://www.iai.uni-bonn.de/~jv/icfp10.pdf Combining Syntactic and Semantic Bidirectionalization]<br />
:Janis Voigtländer, Zhenjiang Hu, Kazutaka Matsuda, Meng Wang. 2010.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/icfp09.pdf Free Theorems Involving Type Constructor Classes]<br />
:Janis Voigtländer. 2009.<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2009/2847/content.pdf Linear, Bounded, Functional Pretty-Printing]<br />
:S. Doaitse Swierstra, Olaf Chitil. 2009.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl09-2.pdf Bidirectionalization for Free!]<br />
:Janis Voigtländer. 2009.<br />
<br />
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP08.pdf Functional Pearl: Streams and Unique Fixed Points]<br />
:Ralf Hinze, ICFP 2008<br />
<br />
;[ftp://ftp.diku.dk/diku/semantics/papers/D-582.pdf Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time]<br />
:Fritz Henglein. 2008<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl202-voigtlaender.pdf Much Ado about Two: A Pearl on Parallel Prefix Computation]<br />
:Janis Voigtländer. 2008.<br />
<br />
;[http://strictlypositive.org/CJ.pdf Clowns to the Left of me, Jokers to the Right: Dissecting Data Structures]: Conor McBride. 2008.<br />
<br />
;[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]<br />
:David Herman. 2007.<br />
<br />
;[https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2007.pdf Scrap Your Zippers]<br />
:Michael Adams. 2007. Superseded by the [https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2010.pdf WGP 2010 version].<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.4086 A type-correct, stack-safe, provably correct expression compiler in Epigram]<br />
:James McKinna and Joel Wright. 2006.<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf Applicative Programming with Effects]<br />
:Conor McBride and Ross Paterson. 2006.<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/rationals.pdf Enumerating the rationals]<br />
:Jeremy Gibbons, David Lester and Richard Bird. 2006.<br />
<br />
;[http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf A program to solve Sudoku]<br />
: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]).<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell]<br />
:Martin Erwig and Steve Kollmansberger. 2006. <br />
<br />
;[http://cms.brookes.ac.uk/staff/SharonCurtis/publications/marbles.ps.gz Marble mingling]<br />
:Sharon Curtis. 2006.<br />
<br />
;[http://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Strong Types for Relational Databases]<br />
:Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)<br />
<br />
;[http://okmij.org/ftp/papers/LogicT.pdf Backtracking, interleaving, and terminating monad transformers]<br />
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005. <br />
<br />
;[http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate]<br />
:James Cheney. 2005.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]<br />
:Andrew Kennedy. 2004.<br />
<br />
;[http://web.cecs.pdx.edu/~mpj/pubs/composing-fractals.pdf Composing fractals]<br />
:Mark P. Jones. 2004.<br />
<br />
;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages]<br />
:M. Douglas McIlroy. 2004.<br />
<br />
;[http://www.kestrel.edu/home/people/meertens/publications/papers/Calculating_the_Sieve_of_Eratosthenes.pdf Calculating the Sieve of Eratosthenes]<br />
: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])<br />
<br />
;[http://pauillac.inria.fr/~maranget/enum/pearl.ps Functional satisfaction]<br />
:Luc Maranget. 2004. ([http://pauillac.inria.fr/~maranget/enum/index.html More info]).<br />
<br />
;[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]<br />
:Oleg Kiselyov, Chung-chieh Shan. 2004. ([http://www.cs.rutgers.edu/~ccshan/prepose/p1214-kiselyov.pdf also here])<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global variables in Haskell]<br />
:John Hughes. 2004. ([http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=241773 JFP])<br />
<br />
;[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]<br />
:Conor McBride, James McKinna. 2004. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform]<br />
:Richard Bird and Shin-Cheng Mu. 2004. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/online/BirdMu2004Inverting.pdf Also here]).<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases]<br />
:Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004.<br />
<br />
;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices]<br />
:Sergio Antoy and Michael Hanus. 2004. <br />
<br />
;[http://www.ling.gu.se/~peb/pubs/Ljunglof-2004b.pdf Functional chart parsing of context-free grammars]<br />
:Peter Ljunglf. 2004.<br />
<br />
;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast]<br />
:Stephanie Weirich. 2004.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]<br />
:Andrew J. Kennedy. 2004.<br />
<br />
;[http://www.cs.chalmers.se/~koen/pubs/jfp04-parser.ps Parallel Parsing Processes]<br />
:Koen Claessen. 2004.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/1.pdf Derivation of a logarithmic time carry lookahead addition circuit]<br />
: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]). <br />
<br />
;[http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest, functionally]<br />
:Jean-Christophe Filliatre and Francois Pottier. 2003.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf Trouble shared is trouble halved]<br />
:Richard Bird, Ralf Hinze. 2003<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Format.ps.gz Formatting: a class act]<br />
:Ralf Hinze. 2003.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz A fresh look at binary search trees]<br />
:Ralf Hinze. 2002.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/countdown.pdf The countdown problem]<br />
:Graham Hutton. 2002. <br />
<br />
;[http://pdos.csail.mit.edu/papers/packrat-parsing:icfp02.pdf Packrat parsing: simple, powerful, lazy, linear time, functional pearl]<br />
:Bryan Ford. 2002.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing]<br />
:Magnus Carlsson. 2002.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/wgp01/hinze-paper.pdf Haskell does it with class: Functorial unparsing]<br />
:Ralf Hinze. 2001.<br />
<br />
<br />
;[http://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms]<br />
:Richard Bird. 2001.<br />
<br />
;[http://eprints.ouls.ox.ac.uk/archive/00000862/01/bird_2001.pdf Maximum marking problems]<br />
:Richard Bird. 2001. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz Weaving a web]<br />
:Ralf Hinze and Johan Jeuring. 2001. <br />
<br />
;[http://www.brics.dk/RS/01/16/BRICS-RS-01-16.pdf Normalization by evaluation with typed abstract syntax]<br />
:Olivier Danvy, Morten Rhiger and Kristoffer H. Rose. 2001. <br />
<br />
;[http://www.brics.dk/RS/01/10/BRICS-RS-01-10.ps.gz Do we need dependent types?]<br />
:Daniel Fridlender and Mia Indrika. 2001.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-99-4.ps.gz Perfect trees and bit-reversal permutations]<br />
:Ralf Hinze. 2000.<br />
<br />
;[http://spivey.oriel.ox.ac.uk/mike/bfs/bfs.ps Combinators for breadth-first search]<br />
:Michael Spivey. 2000 <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design]<br />
:Chris Okasaki. 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers]<br />
:Ralf Hinze. 2000.<br />
<br />
;[http://www.cis.upenn.edu/~bcpierce/papers/rsr.ps Recursive subtyping revealed]<br />
:Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. 2000.<br />
<br />
;[http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/contracts-icfp.ps.gz Composing contracts: an adventure in financial engineering]<br />
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.<br />
<br />
;[http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps A poor man's concurrency monad]<br />
:Koen Claessen. 1999. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/BinomialHeaps.ps.gz Explaining binomial heaps]<br />
:Ralf Hinze. 1999. <br />
<br />
;[http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series, power serious]<br />
:M. Douglas McIlroy. 1999. <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps Red-black trees in a functional setting]<br />
:Chris Okasaki. 1999. <br />
<br />
;[http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]<br />
: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]).<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/radix.ps.gz A pointless derivation of radix sort]<br />
:Jeremy Gibbons. 1999.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell]<br />
:Graham Hutton and Erik Meijer . 1998.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6891 Polytypic unification]<br />
:Patrik Jansson and Johan Jeuring. 1998. <br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf Diets for fat sets]<br />
:Martin Erwig. 1998. <br />
<br />
;[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?]<br />
:Chris Okasaki. 1998.<br />
<br />
;[http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper]<br />
:Gerard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]).<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096 Lazy wheel sieves and spirals of primes]<br />
:Colin Runciman. 1997. <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees]<br />
:Chris Okasaki. 1997. <br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem]<br />
:Jeremy Gibbons. 1996.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/basics.pdf Back to Basics: Deriving Representation Changers Functionally].<br />
:Graham Hutton, Erik Meijer. 1996.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees]<br />
:Andrew J. Kennedy. 1996.<br />
<br />
;[http://research.microsoft.com/~nick/newtrans.pdf Undoing Dynamic Typing]<br />
:Nick Benton. 2008.<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]<br />
:Jeremy Gibbons. 1996. (See also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report]).<br />
<br />
;[http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act]<br />
:Stephen Adams. 1993. ([http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html Data.Set]).<br />
<br />
=== Potential Pearls ===<br />
<br />
Unpublished pearls.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Quote.pdf Typed Quote/AntiQuote]<br />
:Ralf Hinze. Unpublished work in progress.<br />
<br />
;[http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf &alpha;-conversion is easy]<br />
:Thorsten Altenkirch. Unpublished draft.<br />
<br />
=== Offline ===<br />
<br />
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section!<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254707 Linear lambda calculus and PTIME-completeness]<br />
:Harry G. Mairson. 2004. <br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2001/1293/index.html Red-black trees with types]<br />
: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!])<br />
<br />
;On generating unique names<br />
:Lennart Augustsson, M Rittri, D Synek. 1994. ([http://www.cs.chalmers.se/~rittri/#publications Rittri's homepage])<br />
<br />
;A Symmetric Set of Efficient List Operations.<br />
:Rob R. Hoogerwoord, 1992. ([https://venus.tue.nl/ep-cgi/ep_publ.opl?taal=NL&fac_id=92&rn=19840694 Hoogerwoord's homepage]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming]<br />
:Richard Bird and Sharon Curtis. 2006. ([http://cms.brookes.ac.uk/staff/SharonCurtis/publications/index.html#celebrities See also]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254705 On tiling a chessboard]<br />
:Richard Bird. 2004. ([http://portal.acm.org/citation.cfm?id=1030333.1030336 ACM]) <br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44141 Meertens number]<br />
:Richard Bird. 1998.<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=44091 On merging and selection]<br />
:Richard Bird. 1997. (See also [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/merging.ps.gz More on Merging and Selection]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=44107 On building trees with minimum height]<br />
:Richard Bird. 1997. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird97:OnBuilding Bib]).<br />
<br />
;The Last Tail. <br />
:Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird93:Last Bib]).<br />
<br />
;Two Greedy Algorithms<br />
:Richard Bird, 1992. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#Bird92:Two Bib]).<br />
<br />
;On Removing Duplicates<br />
:Richard Bird. 1991. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#DBLP:journals/jfp/Bird91a Bib]).<br />
<br />
[[Category:Research]] [[Category:Tutorials]]</div>Jeremygibbonshttps://wiki.haskell.org/index.php?title=Research_papers/Functional_pearls&diff=42082Research papers/Functional pearls2011-09-15T02:31:32Z<p>Jeremygibbons: </p>
<hr />
<div>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.<br />
<br />
The history of functional pearls is covered by:<br />
<br />
;[http://icfp06.cs.uchicago.edu/bird-talk.pdf How to Write a Functional Pearl]<br />
:Richard Bird. ICFP 2006.<br />
<br />
;[http://portal.acm.org/ft_gateway.cfm?id=1159832&type=pdf&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 Fifteen years of functional pearls]<br />
:Richard Bird. ICFP 2006.<br />
<br />
;[http://spivey.oriel.ox.ac.uk/mike/firstpearl.pdf Strachey's functional pearl, forty years on]<br />
:Mike Spivey, 2006.<br />
<br />
;[http://www.brics.dk/RS/07/14/index.html On Barron and Strachey's Cartesian Product Function]<br />
: Olivier Danvy and Michael Spivey, July 2007<br />
<br />
There have been many functional pearls in JFP, and some others at<br />
ICFP and the Haskell Workshop. There is also a collection of them in<br />
[http://web2.comlab.ox.ac.uk/oucl/publications/books/fop/ The Fun of Programming].<br />
<br />
The pearls tend to concentrate on:<br />
<br />
* Examples of program calculation and proof<br />
* Neat presentations of new or old data structures<br />
* Interesting applications and techniques<br />
<br />
Some advice on writing pearls for JFP is available in this [http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/ editorial].<br />
<br />
=== Online ===<br />
<br />
Functional pearls online:<br />
<br />
;[http://research.microsoft.com/en-us/people/dimitris/every-bit-counts.pdf Every Bit Counts]<br />
:Dimitrios Vytiniotis, Andrew Kennedy. 2010.<br />
<br />
;[http://www.iai.uni-bonn.de/~jv/icfp10.pdf Combining Syntactic and Semantic Bidirectionalization]<br />
:Janis Voigtländer, Zhenjiang Hu, Kazutaka Matsuda, Meng Wang. 2010.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/icfp09.pdf Free Theorems Involving Type Constructor Classes]<br />
:Janis Voigtländer. 2009.<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2009/2847/content.pdf Linear, Bounded, Functional Pretty-Printing]<br />
:S. Doaitse Swierstra, Olaf Chitil. 2009.<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl09-2.pdf Bidirectionalization for Free!]<br />
:Janis Voigtländer. 2009.<br />
<br />
;[http://www.cs.ox.ac.uk/ralf.hinze/publications/ICFP08.pdf Functional Pearl: Streams and Unique Fixed Points]<br />
:Ralf Hinze, ICFP 2008<br />
<br />
;[ftp://ftp.diku.dk/diku/semantics/papers/D-582.pdf Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time]<br />
:Fritz Henglein. 2008<br />
<br />
;[http://wwwtcs.inf.tu-dresden.de/~voigt/popl202-voigtlaender.pdf Much Ado about Two: A Pearl on Parallel Prefix Computation]<br />
:Janis Voigtländer. 2008.<br />
<br />
;[http://strictlypositive.org/CJ.pdf Clowns to the Left of me, Jokers to the Right: Dissecting Data Structures]: Conor McBride. 2008.<br />
<br />
;[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]<br />
:David Herman. 2007.<br />
<br />
;[https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2007.pdf Scrap Your Zippers]<br />
:Michael Adams. 2007. Superseded by the [https://www.cs.indiana.edu/~adamsmd/papers/scrap_your_zippers/ScrapYourZippers-2010.pdf WGP 2010 version].<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.4086 A type-correct, stack-safe, provably correct expression compiler in Epigram]<br />
:James McKinna and Joel Wright. 2006.<br />
<br />
;[http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf Applicative Programming with Effects]<br />
:Conor McBride and Ross Paterson. 2006.<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/rationals.pdf Enumerating the rationals]<br />
:Jeremy Gibbons, David Lester and Richard Bird. 2006.<br />
<br />
;[http://www.cs.tufts.edu/~nr/comp150fp/archive/richard-bird/sudoku.pdf A program to solve Sudoku]<br />
: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]).<br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/PFP_JFP06.pdf Probabilistic functional programming in Haskell]<br />
:Martin Erwig and Steve Kollmansberger. 2006. <br />
<br />
;[http://cms.brookes.ac.uk/staff/SharonCurtis/publications/marbles.ps.gz Marble mingling]<br />
:Sharon Curtis. 2006.<br />
<br />
;[http://wiki.di.uminho.pt/twiki/pub/Personal/Xana/WebHome/report.pdf Strong Types for Relational Databases]<br />
:Alexandra Silva, Joost Visser. 2006. (Haskell Workshop)<br />
<br />
;[http://okmij.org/ftp/papers/LogicT.pdf Backtracking, interleaving, and terminating monad transformers]<br />
:Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry. 2005. <br />
<br />
;[http://homepages.inf.ed.ac.uk/jcheney/publications/cheney05icfp.pdf Scrap your Nameplate]<br />
:James Cheney. 2005.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]<br />
:Andrew Kennedy. 2004.<br />
<br />
;[http://web.cecs.pdx.edu/~mpj/pubs/composing-fractals.pdf Composing fractals]<br />
:Mark P. Jones. 2004.<br />
<br />
;[http://www.cs.dartmouth.edu/~doug/nfa.ps.gz Enumerating the strings of regular languages]<br />
:M. Douglas McIlroy. 2004.<br />
<br />
;[http://pauillac.inria.fr/~maranget/enum/pearl.ps Functional satisfaction]<br />
:Luc Maranget. 2004. ([http://pauillac.inria.fr/~maranget/enum/index.html More info]).<br />
<br />
;[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]<br />
:Oleg Kiselyov, Chung-chieh Shan. 2004. ([http://www.cs.rutgers.edu/~ccshan/prepose/p1214-kiselyov.pdf also here])<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.145&rep=rep1&type=ps Global variables in Haskell]<br />
:John Hughes. 2004. ([http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=241773 JFP])<br />
<br />
;[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]<br />
:Conor McBride, James McKinna. 2004. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/2.ps.gz Inverting the Burrows Wheeler transform]<br />
:Richard Bird and Shin-Cheng Mu. 2004. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/online/BirdMu2004Inverting.pdf Also here]).<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/wg21/meeting56/loeh-paper.pdf Parsing permutation phrases]<br />
:Arthur Baars, Andres Loh and S. Doaitse Swierstra. 2004.<br />
<br />
;[http://web.cecs.pdx.edu/~antoy/homepage/publications/inject/paper.pdf Concurrent distinct choices]<br />
:Sergio Antoy and Michael Hanus. 2004. <br />
<br />
;[http://www.ling.gu.se/~peb/pubs/Ljunglof-2004b.pdf Functional chart parsing of context-free grammars]<br />
:Peter Ljunglf. 2004.<br />
<br />
;[http://www.seas.upenn.edu/~sweirich/papers/cast/cast.pdf Type-Safe Cast]<br />
:Stephanie Weirich. 2004.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/picklercombinators.pdf Pickler Combinators]<br />
:Andrew J. Kennedy. 2004.<br />
<br />
;[http://www.cs.chalmers.se/~koen/pubs/jfp04-parser.ps Parallel Parsing Processes]<br />
:Koen Claessen. 2004.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/hw2001/1.pdf Derivation of a logarithmic time carry lookahead addition circuit]<br />
: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]). <br />
<br />
;[http://www.lri.fr/~filliatr/ftp/publis/kr-fp.ps.gz Producing all ideals of a forest, functionally]<br />
:Jean-Christophe Filliatre and Francois Pottier. 2003.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf Trouble shared is trouble halved]<br />
:Richard Bird, Ralf Hinze. 2003<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Format.ps.gz Formatting: a class act]<br />
:Ralf Hinze. 2003.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz A fresh look at binary search trees]<br />
:Ralf Hinze. 2002.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/countdown.pdf The countdown problem]<br />
:Graham Hutton. 2002. <br />
<br />
;[http://pdos.csail.mit.edu/papers/packrat-parsing:icfp02.pdf Packrat parsing: simple, powerful, lazy, linear time, functional pearl]<br />
:Bryan Ford. 2002.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.3014 Monads for Incremental Computing]<br />
:Magnus Carlsson. 2002.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/wgp01/hinze-paper.pdf Haskell does it with class: Functorial unparsing]<br />
:Ralf Hinze. 2001.<br />
<br />
<br />
;[http://eprints.ouls.ox.ac.uk/archive/00000863/01/bird_2001_11_3.pdf Unfolding pointer algorithms]<br />
:Richard Bird. 2001.<br />
<br />
;[http://eprints.ouls.ox.ac.uk/archive/00000862/01/bird_2001.pdf Maximum marking problems]<br />
:Richard Bird. 2001. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz Weaving a web]<br />
:Ralf Hinze and Johan Jeuring. 2001. <br />
<br />
;[http://www.brics.dk/RS/01/16/BRICS-RS-01-16.pdf Normalization by evaluation with typed abstract syntax]<br />
:Olivier Danvy, Morten Rhiger and Kristoffer H. Rose. 2001. <br />
<br />
;[http://www.brics.dk/RS/01/10/BRICS-RS-01-10.ps.gz Do we need dependent types?]<br />
:Daniel Fridlender and Mia Indrika. 2001.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/IAI-TR-99-4.ps.gz Perfect trees and bit-reversal permutations]<br />
:Ralf Hinze. 2000.<br />
<br />
;[http://spivey.oriel.ox.ac.uk/mike/bfs/bfs.ps Combinators for breadth-first search]<br />
:Michael Spivey. 2000 <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design]<br />
:Chris Okasaki. 2000.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/ICFP00.ps.gz Deriving Backtracking Monad Transformers]<br />
:Ralf Hinze. 2000.<br />
<br />
;[http://www.cis.upenn.edu/~bcpierce/papers/rsr.ps Recursive subtyping revealed]<br />
:Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. 2000.<br />
<br />
;[http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/contracts-icfp.ps.gz Composing contracts: an adventure in financial engineering]<br />
:Simon Peyton Jones, Jean-Marc Eber, Julian Seward. 2000.<br />
<br />
;[http://www.cs.chalmers.se/~koen/pubs/jfp99-monad.ps A poor man's concurrency monad]<br />
:Koen Claessen. 1999. <br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/BinomialHeaps.ps.gz Explaining binomial heaps]<br />
:Ralf Hinze. 1999. <br />
<br />
;[http://www.cs.dartmouth.edu/~doug/pearl.ps.gz Power series, power serious]<br />
:M. Douglas McIlroy. 1999. <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp99.ps Red-black trees in a functional setting]<br />
:Chris Okasaki. 1999. <br />
<br />
;[http://www.cs.cmu.edu/~rwh/papers/regexp/jfp.ps Proof-directed debugging]<br />
: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]).<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/radix.ps.gz A pointless derivation of radix sort]<br />
:Jeremy Gibbons. 1999.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/pearl.pdf Monadic parsing in Haskell]<br />
:Graham Hutton and Erik Meijer . 1998.<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6891 Polytypic unification]<br />
:Patrik Jansson and Johan Jeuring. 1998. <br />
<br />
;[http://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf Diets for fat sets]<br />
:Martin Erwig. 1998. <br />
<br />
;[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?]<br />
:Chris Okasaki. 1998.<br />
<br />
;[http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf The Zipper]<br />
:Gerard Huet. 1997. (See also [http://en.wikibooks.org/wiki/Haskell/Zippers The Haskell Wikibook]).<br />
<br />
;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096 Lazy wheel sieves and spirals of primes]<br />
:Colin Runciman. 1997. <br />
<br />
;[http://www.eecs.usma.edu/webs/people/okasaki/jfp97.ps Three algorithms on Braun trees]<br />
:Chris Okasaki. 1997. <br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/thirdht.ps.gz The Third Homomorphism Theorem]<br />
:Jeremy Gibbons. 1996.<br />
<br />
;[http://www.cs.nott.ac.uk/~gmh/basics.pdf Back to Basics: Deriving Representation Changers Functionally].<br />
:Graham Hutton, Erik Meijer. 1996.<br />
<br />
;[http://research.microsoft.com/~akenn/fun/DrawingTrees.pdf Drawing Trees]<br />
:Andrew J. Kennedy. 1996.<br />
<br />
;[http://research.microsoft.com/~nick/newtrans.pdf Undoing Dynamic Typing]<br />
:Nick Benton. 2008.<br />
<br />
;[http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/drawing.ps.gz Deriving Tidy Drawings of Trees]<br />
:Jeremy Gibbons. 1996. (See also [http://www.cs.auckland.ac.nz/CDMTCS//researchreports/003drawing.pdf the research report]).<br />
<br />
;[http://groups.csail.mit.edu/mac/users/adams/BB/ Efficient Sets - A Balancing Act]<br />
:Stephen Adams. 1993. ([http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html Data.Set]).<br />
<br />
=== Potential Pearls ===<br />
<br />
Unpublished pearls.<br />
<br />
;[http://www.informatik.uni-bonn.de/~ralf/publications/Quote.pdf Typed Quote/AntiQuote]<br />
:Ralf Hinze. Unpublished work in progress.<br />
<br />
;[http://www.cs.nott.ac.uk/~txa/publ/alpha-draft.pdf &alpha;-conversion is easy]<br />
:Thorsten Altenkirch. Unpublished draft.<br />
<br />
=== Offline ===<br />
<br />
These appear not to be available online, unfortunately. If you know where they live, please link, and move into the 'online' section!<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254707 Linear lambda calculus and PTIME-completeness]<br />
:Harry G. Mairson. 2004. <br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254723 Calculating the Sieve of Eratosthenes]<br />
: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])<br />
<br />
;[http://www.cs.kent.ac.uk/pubs/2001/1293/index.html Red-black trees with types]<br />
: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!])<br />
<br />
;On generating unique names<br />
:Lennart Augustsson, M Rittri, D Synek. 1994. ([http://www.cs.chalmers.se/~rittri/#publications Rittri's homepage])<br />
<br />
;A Symmetric Set of Efficient List Operations.<br />
:Rob R. Hoogerwoord, 1992. ([https://venus.tue.nl/ep-cgi/ep_publ.opl?taal=NL&fac_id=92&rn=19840694 Hoogerwoord's homepage]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=335124 Finding celebrities: A lesson in functional programming]<br />
:Richard Bird and Sharon Curtis. 2006. ([http://cms.brookes.ac.uk/staff/SharonCurtis/publications/index.html#celebrities See also]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=254705 On tiling a chessboard]<br />
:Richard Bird. 2004. ([http://portal.acm.org/citation.cfm?id=1030333.1030336 ACM]) <br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=44141 Meertens number]<br />
:Richard Bird. 1998.<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=44091 On merging and selection]<br />
:Richard Bird. 1997. (See also [http://web.comlab.ox.ac.uk/people/Jeremy.Gibbons/publications/merging.ps.gz More on Merging and Selection]).<br />
<br />
;[http://journals.cambridge.org/action/displayAbstract?aid=44107 On building trees with minimum height]<br />
:Richard Bird. 1997. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird97:OnBuilding Bib]).<br />
<br />
;The Last Tail. <br />
:Richard Bird. 1993. ([http://web.comlab.ox.ac.uk/people/Richard.Bird/publications-bib.html#Bird93:Last Bib]).<br />
<br />
;Two Greedy Algorithms<br />
:Richard Bird, 1992. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#Bird92:Two Bib]).<br />
<br />
;On Removing Duplicates<br />
:Richard Bird. 1991. ([http://web.comlab.ox.ac.uk/oucl/work/richard.bird/publications-bib.html#DBLP:journals/jfp/Bird91a Bib]).<br />
<br />
[[Category:Research]] [[Category:Tutorials]]</div>Jeremygibbonshttps://wiki.haskell.org/index.php?title=Talk:SantaClausProblemV2&diff=10630Talk:SantaClausProblemV22007-01-22T12:47:14Z<p>Jeremygibbons: </p>
<hr />
<div>= Beautiful concurrency =<br />
<br />
I am writing a chapter for a book called "Beautiful code", edited by Greg Wilson. The chapter is a tutorial about Software Transactional Memory in Haskell.<br />
<br />
After a lot of useful feedback, I have now completed [http://research.microsoft.com/~simonpj/papers/stm/beautiful.ps Version 2] of the paper. The [http://research.microsoft.com/~simonpj/papers/stm/Santa.hs.gz Haskell code] is also available.<br />
<br />
I would welcome any comments or questions you have on the paper, or constructive suggestions for improving it; the more concrete the better. You can see what people said about version 1 on the version 1 talk page: [[Talk:SantaClausProblem ]].<br />
<br />
The book is aimed at a general audience of programmers, <em>not</em> Haskell geeks, so I have tried to explain everything necessary as I go along. So if you are not a Haskell expert, your input would be particularly valuable to me.<br />
<br />
You can email me directly (simonpj@microsoft.com), or add Wiki talk notes below.<br />
<br />
If you give your real name somewhere in your text (or email it to me), I'll add you to the acknowledgements at the end of the chapter. Notably, I'd like to acknowledge Steven807, Tibbe, Fanf, Garious, Rycee, Brecknell, Mvanier, Gaal, Fernando, Gknauth, EngineerScotty, BoAdler.<br />
<br />
----------<br />
<br />
[[User:Simonpj|Simonpj]] 14:26, 22 December 2006 (UTC) To add a note, begin with four tilde signs <nowiki>~~~~</nowiki>; the Wiki will fill in your user name and date.<br />
<br />
[[User:Brecknell|Brecknell]] 13:38, 11 January 2007 (UTC) In Figure 1, retry should be STM a, not STM ().<br />
<br />
[[User:Schmitz|Sylvain]] 13:45, 11 January 2007 (UTC) small points: since you go through explaining that the do-notation is overloaded and works for STM as well as IO (page 8), you might want to tell the same for return on page 11 (return being given with a type a -> IO a on page 5). There is also a double "Here is the code" at the bottom of page 17.<br />
<br />
[[User:Brecknell|Brecknell]] 13:59, 11 January 2007 (UTC) The rewrite of the paragraph at top of page 17 has left behind a fragment that I think just needs to be deleted: "just runs each of the actions in sequence".<br />
<br />
[[User:Brecknell|Brecknell]] 14:15, 11 January 2007 (UTC) Last sentence of page 18: "Here is another way approach that..." Delete either "way" or "approach".<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 14:27, 11 January 2007 (UTC) minor stuff, really: <br />
* page 2, middle of page: syncrhonized -> synchronized<br />
* page 5, top of page: For example, here are two Haskell functions -> For example, here are the type signatures for two Haskell functions (the functions themselves may be primitives, after all)<br />
* page 5, second paragraph: do the parentheses around hPutStr serve more than to confuse? Especially given their absence for hEchoLine...<br />
* page 5, footnote 3: comma after effects<br />
* page 6: make discarding the return value of forkIO in the second example main more explicit, e.g. with a footnote<br />
* page 7, after Atomicity: This ensured -> This ensures<br />
<br />
[[User:Brecknell|Brecknell]] 14:32, 11 January 2007 (UTC) I like the way you build up to the definition of "choose" in this new revision. I think this helps to convey how STM and actions as first-class values can improve modularity and composability in concurrent applications. So, if you like, you can consider my lsat comment on the previous revision "done", as well.<br />
<br />
[[User:Maeder|Maeder]] 14:38, 11 January 2007 (UTC) <br />
* page 11, use subtract (+ -> -) in limitedWithDraw<br />
* page 22 (2nd line), the the -> the<br />
<br />
[[User:Genneth|Genneth]] 15:07, 11 January 2007 (UTC) p4: make analogy between () and void to help non-haskellers<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 15:10, 11 January 2007 (UTC) The bottom of page 17 has 'Here is his code:' in duplicate.<br />
<br />
[[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] 15:19, 11 January 2007 (UTC) The note 'The code for choose is brief, but a little mind-bending:' on page 19 is very short, for such a leap in required understanding. In just one single block of 7 lines you introduce both the concept of IO actions encapsulated inside STM actions as well as the concept of list comprehension. For a non-haskeller this is quite a lot.<br />
<br />
[[User:Maeder|Maeder]] 15:25, 11 January 2007 (UTC) maybe generalize nTimes on page 7 to type: Int -> (Int -> IO ()) -> IO ()<br />
and use nTimes on page 16 instead of sequence_ and list comprehensions. (The function choose on page 19 is also higher order.)<br />
<br />
[[User:Malcolm|Malcolm]] 15:27, 11 January 2007 (UTC)<br />
* Intro, para 2, "Sadly, parallel program[s] are" - missing plural<br />
* sec 2.1, para 3, "if two thread[s] call" - missing plural<br />
* sec 3.2, Atomicity, "This ensured that" -> "This ensures that"<br />
<br />
[[User:Maeder|Maeder]] 15:35, 11 January 2007 (UTC) maybe use putStrLn (hPutStrLn) instead of \n in the strings<br />
<br />
[[User:Malcolm|Malcolm]] 16:07, 11 January 2007 (UTC)<br />
* page 11, limitedWithdraw2 in type signature, is called simply withdraw2 in definition<br />
* sec 4.2 "remaining capactity" -> "remaining capacity" (x3)<br />
* sec 4.3 "newGate makes [a] new Gate" - missing article<br />
* top of page 17, orphan (non-)sentence ". just runs each of the actions in sequence."<br />
* sec 4.4, "futher" -> "further"<br />
* sec 4.4 "another way approach" -> "another approach"<br />
* sec 6 "exectued" -> "executed"<br />
* sec 6 "the the treatment" -> "the treatment"<br />
[[User:Jmuk|Jmuk]] 04:14, 12 January 2007 (UTC) page 13, semicolons in helper1 are out of alignment<br />
<br />
[[User:Fanf|Fanf]] 19:34, 12 January 2007 (UTC) Minor nits:<br />
* p.2: need semicolon at end of last java statement in each function.<br />
* p.2: should you comment that the class has a withdraw method similar to the deposit method?<br />
* p.4 paragraph about locks: you introduce the word "compositional" here - perhaps better to stick with "modular"?<br />
* bottom of p. 4: should "can" be omitted, or should it read "we must explain"?<br />
* bottom of p. 7: inconsistent tense: began -> begins.<br />
* Should the layout of the do notation be more like normal C layout, to avoid freaking out the mundanes?<br />
* would openGate be a clearer name for operateGate?<br />
* footnote p. 14: mkGate -> MkGate<br />
* santa's code: perhaps a comment between two gates to note that the elves or reindeers do their things at that point.<br />
* limitedWithdraw: is the test (amount > 0) redundant?<br />
<br />
[[User:Fanf|Fanf]] 19:45, 12 January 2007 (UTC) Section 4 introduction: The description of the problem reads like a description of an implementation, and I think it should be more story-like. e.g.<br />
<br />
Santa spends most of his time asleep. On Christmas Eve, his nine reindeer return from their holidays and wake up Santa. He harnesses each of them to his sleigh,<br />
delivers toys with them and finally unharnesses them, allowing them<br />
to return to their holidays. All year his ten elves are busy working to make toys, but every so often they will need to consult Santa about toy R&D in his study. Santa will only wake up and talk to three of them at a time, and of course their consultations are a lower priority than delivering toys.<br />
<br />
* p.13 perhaps "sleep" should be "delay" for consistency with the terminology in the code, and to avoid confusion with what santa does - the elves are making toys during the delay, not sleeping.<br />
* Also, is it worth noting that the reindeer gates model the harnessing and unharnessing?<br />
<br />
[[User:M4dc4p|Justin Bailey]] 20:35, 12 January 2007 (UTC) Really interesting paper. I've only been exposed to Haskell (through a graduate Programming Languages course) for 4 or 5 months, but I found it very readable. My comments:<br />
<br />
* The introduction showing problems with locks and how atomically can be used in the bank account example is very well done. <br />
* Development of the gate operations is pretty clear. It would have helped if a short gloss on the connection between the whimsical problem statement and the opening/closing of gates was made. Re-reading, you do cover it in one paragraph on p.13. Sadly, I'd forgotten a lot of that by the time I got to reading about the implementation of Gates and Groups. Maybe make connections throughout that section?<br />
* I agree with [[User:ArthurVanLeeuwen|ArthurVanLeeuwen]] above about the ''choose'' function. It's extremely mind-bending. I didn't event notice ''actions'' was a list until I saw the post - I just skimmed past that syntax trying to figure out the do portion. I also think the introduction of foldr1 would throw people not familiar with Haskell or functional programming. I still have trouble with it :)<br />
* p.14: "capacity" is misspelled "capactity" several times.<br />
* p.17: "1000,000 microseconds" instead of "1,000,000 microseconds".<br />
<br />
[[User:LuciusGregoryMeredith|LuciusGregoryMeredith]] 02:00, 13 January 2007 (UTC) Simon, lovely paper. Your first paragraph is very compelling. Let me quote it here.<br />
* "The free lunch is over [8]. We have grown used to the idea that our programs will go faster when we buy a next-generation processor, but that time has passed. While that next-generation chip will have more CPUs, each individual CPU will be no faster than the previous year’s model. If we want our program to run faster, we must learn to write parallel programs [9]."<br />
* What evidence does this paper offer that using STM will actually get my program to run faster? For all i can see in this example, it may be a beautiful abstraction that when used at scale on interesting programs cannot actually take advantage of the multicore architecture. To be convinced, starting from this particularly motivating opening, i would like to see an example that begins with an algorithm that is not parallel. Then be shown a beautiful, STM-based parallel version that is demonstrably faster.<br />
* It would be particularly compelling to see just how a good implementation of STM for Haskell takes advantage of Intel and/or AMD multicore hardware. <br />
* It would be even more compelling to see the corresponding lock-based program and how it fairs relative to the STM version in terms of performance, usage of the hardware platform as well as program understandability and analysis.<br />
* Clearly, one of the real rubs is getting from current expressions of algorithms to parallel ones, especially parallel ones that map onto modern architectures. Perhaps your point is that STM helps one start to think and conceptualize computation as a concurrent activity -- which then offers some hope to the ordinary programmer to develop programs that will actually take advantage of today and tomorrow's architectures. If so, then the paper is an excellent start, but i would very much like to see this point made more explicit and central, especially if you only give some lipservice to the argument that STM can actually be made to take advantage of the multicore architectures. In particular, evidence for this sort of point might come in the form of a study of how long it takes an ''ordinary'' programmer -- not a Simon P-J -- to develop a beautiful solution like a solution to the Santa Clause problem.<br />
* Evidence against this sort of point would come in the form of people finding the basic constructs of the solution "mind-bending".<br />
<br />
[[User:Pitarou|Pitarou]] 00:51, 15 January 2007 (UTC) In the definition of the function <hask>forever</hask>, there is the comment <hask>-- Repeatedly perform the action, taking a rest each time</hask>. I'm not sure what you mean by "taking a rest".<br />
<br />
[[User:Asilovy|Asilovy]] 16:43, 15 January 2007 (UTC) Page 1 first paragraph, last sentence : I'm not native english but I wonder if you would'nt write "If we want our programs..." with 's' since you use plurals elswhere.<br />
<br />
[[User:Asilovy|Asilovy]] 16:43, 15 January 2007 (UTC) Page 3 last sentence before 2.2 : Is'nt it "... on there being INsufficient..." rather than "sufficient" ?<br />
<br />
[[User:Asilovy|Asilovy]] 18:33, 15 January 2007 (UTC) Page 6, last sentence : Should'nt you write "...being explicit aboute SIDE effects..." and the same for the last sentence of the next paragraph (begin page 7) "This ability to make SIDE effects..."<br />
<br />
[[User:Asilovy|Asilovy]] 18:33, 15 January 2007 (UTC) Page 8 second paragraph : I can understand that, in some sense, atomocity and isolation are related (in fact 2 faces seen by different threads of the same problem) but you start by saying the model does not ensure atomicity and explain why finishing by "...thereby destroying the isolation guarantee". Sounds confusing.<br />
<br />
[[User:Asilovy|Asilovy]] 18:33, 15 January 2007 (UTC) Page 10 code of limitedWithdraw : isn't it "writeTVar acc (bal - amount)" with a minus ?<br />
<br />
[[User:Asilovy|Asilovy]] 18:33, 15 January 2007 (UTC) Page 11 : name confusion in the code to limitedWithdraw2 (in the type signature), and withdraw2 in the definition and the comment<br />
<br />
[[User:Asilovy|Asilovy]] 18:33, 15 January 2007 (UTC) Page 15 firt line : maybe "The function newGate makes A new Gate..." ?<br />
<br />
[[User:Jeremygibbons|Jeremygibbons]] 12:47, 22 January 2007 (UTC) "in reality" (p14) - I hate to break it to you, Simon, but I think "in the specification" would be more appropriate here. Also, on p19, "a atomic" should be "an atomic" and on p21, "sophisiticated" is misspelt.</div>Jeremygibbonshttps://wiki.haskell.org/index.php?title=Talk:History_of_Haskell/Timeline&diff=5746Talk:History of Haskell/Timeline2006-08-31T19:54:39Z<p>Jeremygibbons: 0th and 1st IOHCC</p>
<hr />
<div>= Timeline for "The History of Haskell" =<br />
<br />
One of the suggestions made last month was that we add a pictorial time-line of the development of Haskell. Bernie Pope and Don Stewart have been kind enough to do just that. Here is the [http://www.cs.mu.oz.au/~bjpop/timeline/timeline.4.png current draft]<br />
<br />
Would you like to take a look, and let us know about<br />
* factual errors?<br />
* suggestions for things we might consider adding or omitting?<br />
<br />
Of course, we can't include everything! But do feel free to suggest things.<br />
<br />
== Comments ==<br />
<br />
Just add comments here, preceded by "<nowiki>~~~~</nowiki>"<br />
<br />
[[User:Malcolm|Malcolm]] 14:27, 31 August 2006 (UTC) Error: first release of HaXml was April 1999, not Jan 2001 as shown.<br />
<br />
[[User:CaleGibbard|CaleGibbard]] 19:45, 31 August 2006 (UTC) Some things to consider for inclusion would be Don Stewart's projects hs-plugins and Data.ByteString, seeing as the chart is a little thin for the recent years, and these libraries open up the possibility of using Haskell for entirely new kinds of projects.<br />
<br />
[[User:Jeremygibbons|Jeremygibbons]] 19:54, 31 August 2006 (UTC) It was nice to see the mythical Bottomth International Obfuscated Haskell Code Contest mentioned, but sad not to see the [http://iohcc.mgoetze.net/ Zeroth International Obfuscated Haskell Code Contest] in 2003, and (since I have a personal interest) the [http://www.haskell.org/hawiki/ObfuscatedHaskellContest Succ Zeroth International Obfuscated Haskell Code Contest] in 2004.</div>Jeremygibbons