Mark Spezzano wrote:
Because Haskell is not OO, it is functional, I was wondering if there is some kind of analogous “design pattern”/”template” type concept that describe commonly used functions that can be “factored out” in a general sense to provide the same kind of usefulness that Design Patterns do for OOP. Basically I’m asking if there are any kinds of “common denominator” function compositions that are used again and again to solve problems. If so, what are they called?
Most of the (particular) problems OO design patterns solve are non-issues in Haskell because the language is more expressive. The issues giving rise to patterns like Visitor and Factory are non-issues, so their "solutions" are trivial. A number of other patterns can actually be written down once and for all (in higher-order functions like foldr, map,...) instead of needing repetition. But that's not to say we don't have our own expressiveness deficiencies ;) The analogous term for the genre is "functional pearl", though the individual pearls don't tend to be as codified as in OOP. One example is using coproducts for open unions[1] which solves the dual problem to Visitor. Another is using open recursion[2]. A third example along the same track is using two-level types[3]. But again a lot of the patterns, once discovered, get turned into libraries that can be used off the shelf: e.g. the two-continuation solution for efficient and fair backtracking search[4], and list-fusion techniques[5]. There also a number of "idioms" which are similar in scope to the idioms that arise in other languages: using tail recursion, accumulators, continuation-passing transformations, closures over recursion[6], Schwartzian transforms, etc. And then there are some things like monoids which fall somewhere between idiom and pearl. Some specific OO patterns have direct analogues in "defunctionalization"[7]. For the most part defunctionalization is something best left to the compiler, but on occasion we want to be explicit about it and this too is an idiom/pearl border case IMO. And, of course, there's the entire cottage industry of using category theory for fun and profit. [1] http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf [2] http://www.cs.utexas.edu/~wcook/Drafts/2006/MemoMixins.pdf [3a] http://web.cecs.pdx.edu/~sheard/papers/generic.ps [3b] http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps [4a] http://okmij.org/ftp/papers/LogicT.pdf [4b] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/logict [5a] http://www.cse.unsw.edu.au/~dons/papers/CSL06.html [5b] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bytestring [5c] http://www.cse.unsw.edu.au/~dons/papers/CLS07.html [5d] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion [5e] http://homepages.inf.ed.ac.uk/wadler/papers/vanish/vanish.pdf [6] For lack of a better name. I mean doing this:
-- Here the a,b,c,d variables are captured in the closure for go recursive a b c d = go where go 0 = ...a...b... go n = ...c...d...go (n-1)
instead of this:
-- ...instead of needing to be passed through the recursion each time recursive a b c d 0 = ...a...b... recursive a b c d n = ...c...d...recursive a b c d (n-1)
[7a] http://blog.plover.com/prog/defunctionalization.html -- Live well, ~wren