catamorphisms and visitors (in Ruby)

Pretty much all the examples I found were in Haskell. After reading a few I settled on Understanding F-Algebras and I’m going to use it as my running example.

Translating the types is easy. Given Ruby’s dynamic nature we don’t have to worry about fixed points and type parameters because we get it for free. So our types end up being

Notice that we implement map because F-algebras are defined in terms of functors and functor instances need a notion of map. I’ve also added some operators to make constructing expression trees easier. Given the above definition we can construct expressions like the following

The translation of the F-algebras is also pretty simple because they are just functions.

The first one just evaluates the expression tree in the obvious way and the second one pretty prints the expression by putting parentheses around addition to follow the usual rules of precedence for arithmetic operators. Notice the lack of recursion and the fact that they only work for expressions that are nested one level deep, e.g. Const[1], Add[1, 2], Mult[2, 3], etc.

With that out of the way we can now define catamorphisms. We need to open up some of our data types and add a cata method that takes the algebra morphism and performs the traversal to reduce the compound structure to a value

With all of that out of the way we can now evaluate some expressions

This is all nice and well and we could abstract the definition of cata into a module and include it in any class that implements map but I’m not sure if doing all this in Ruby is worth it. We could have accomplished all the above transformations with simple visitors.

For the visitor approach we just open up each class and add a visit method that just calls whatever is passed in with the first parameter set to self. In fact we can just add this method in the superclass

With some small modifications we can turn the algebras we defined above into visitors

There is another definition of map for Const that works in Ruby but is impossible to type-check in Haskell. Here are the additions

See if you can figure out why this is invalid from the perspective of a statically typed language.