[Haskell-cafe] Functors and the Visitor Pattern

[wren ng thornton]

Tom.Amundsen wrote:
> So, last night, I was having this problem with my Java code where I couldn't
> figure out for the life of me how to write a piece of code without a big if
> {} else if {} else if {} ... else {} structure. I was Googling "Java
> Reflection" to try to determine how to "cast to the most concerete subclass
> at runtime." Then it dawned on me that what I was trying to do has already
> been solved by using the Visitor design pattern.
> 
> Then, after reading the Visitor design pattern page on Wiki, it said that
> the visitor pattern is essentially an implementation of a functor. Aha! It
> totally clicked. The Visitor pattern allows you to collect code for similar
> operations, while spreading apart code for similar objects. Now that really
> sounds like a functor!
> 
> Although, now I'm second guessing myself, because I can't figure out how we
> could create some design pattern that simulates an applicative functor. I'm
> pretty sure the Visitor pattern doesn't take you this far (but I am willing
> to be corrected). So, is there a way to create applicative functors in
> non-functional languages? What would that pattern look like?

The Visitor pattern isn't a functor, it's a collection of things. The 
type being visited is the functor[1], the set of methods on that type 
for accepting a visitor is a catamorphism[2], and the visitor itself is 
an algebra for the functor[3].


[1] Or rather, the coproduct of all related classes that can chain a 
visitor forms a type, and that type is a functor.


[2] For the recursive Visitor pattern I use most often, that is. For the 
non-recursive version it's usually fmap. This is the part where the 
pattern gets a bit shaky because there are actually many different 
patterns all called "Visitor". The main points of interest are whether 
it's recursive or not, and whether it applies the visitor to itself, to 
its children, or both.

non-recursive + itself == ($)

non-recursive + children == fmap (under open-recursion interpretation of 
the type, aka all nodes are elements)

recursive + children == fmap (under closed-recursion interpretation, aka 
only fringe nodes are elements)

recursive + both == cata (usually, though it depends how you aggregate)

recursive + itself == This is actually a variant of the Iterator pattern


[3] Though again there's some variation in different "Visitor" patterns. 
Some variants of the pattern include some of the recursion pattern in 
the visitor itself rather than in the methods on the visited type. It 
can be harder to maintain since it's less modular, though it allows the 
visit methods to serve as many different functions which can be helpful 
if you need more than one of ($), fmap, cata, traverse,...

-- 
Live well,
~wren