# [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,
~wren


More information about the Haskell-Cafe mailing list