[Haskell-cafe] Design Patterns by Gamma or equivalent

wren ng thornton wren at freegeek.org
Wed Mar 18 01:05:05 EDT 2009

Gregg Reynolds wrote:
> Imperative programmers also used it to describe programming patterns.
> Implementations of things like Observer/VIsitor etc. are ad-hoc,
> informal constructions; the equivalent in a functional language is a
> mathematical structure (feel free to fix my terminology).  I don't
> think one needs design patterns for Haskell; it has mathematics and
> more-or-less formal semantics.  Who needs "Visitor" when you have "For
> All"?

In broad strokes I agree with the thesis, but this example is precisely 
one where functional languages run into the same issues as OO languages.

The Visitor pattern is obviated in functional languages if and only if 
you construct your recursive types as a fixed-point on a functor 
representing the open recursive form of your type. Given this you can 
invoke category-extras or similar libraries[1] to tie everything 
together for you. Otherwise you end up writing boilerplate functions 
which are groundings of cata and other recursion schemes.

In the Visitor pattern the visitor itself is your F-algebra, and each 
subtype of \mu F defines its piece of cata (in order to reflect the 
algebra back on itself and to tell it where to recurse). The algebra has 
to be written no matter what, since it's the one that does the real 
work. With category-extras you can define a single implementation of 
cata which works for all F; without it you write boilerplate groundings 
of cata for your specific F, exactly as in the Visitor pattern.

With a sufficiently expressive reflection system in OO you can do the 
same CT trick and use introspection to determine the pieces of cata. The 
functional CT version is generally cleaner, more efficient, and safer, 
but it still requires taking the steps toward CT as a templating 
language since functional programming by itself doesn't obviate the 
Visitor problem.

[1] Similar to OO reflection, you could instead use Template Haskell to 
crack open fixed-recursion types into their open-recursion variants and 
generate an instance of some Cata class, but once more it's the same 
trick all over again.

Live well,

More information about the Haskell-Cafe mailing list