[Haskell-cafe] Design Patterns by Gamma or equivalent

[wren ng thornton]

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