# Implementing a catamorphism for Expression Trees

I am trying to implement an expression tree in Haskell as follows:

``````data ExprTr a b =
Variable a
| Constant b
| Add (ExprTr a b) (ExprTr a b)
| Mul (ExprTr a b) (ExprTr a b)
deriving (Eq, Show)
``````

And I would like to be able to implement operations on it using a catamorphism.

Currently, this is the function I got:

``````cataTr f _ _ _ (Variable i) = f i
cataTr f g _ _ (Constant i) = g i
cataTr f g h i (Add e1 e2) = g (cataTr f g h i e1) (cataTr f g h i e2)
cataTr f g h i (Mul e1 e2) = h (cataTr f g h i e1) (cataTr f g h i e2)
``````

However, whenever I try to use it with an expresion of type `ExprTr String Integer` I get compiler errors. For example, running `cataTr id id id id (Var "X")` returns the following compiler error instead of `(Var "X")`.

``````Couldn't match type 'Integer' with '[Char]'
Expected type: 'ExprTr String String'
Actual type: 'ExprTr String Integer'
``````

I am not sure how to proceed. Furthermore, I would appreciate some suggestions on how to type such a function as cataTr to make it easier to debug later.

As I am fairly new to Haskell, I would like to understand how to approach such situations from 'first principles' instead of using a library to generate the catamorphism for myself.

Solution

• This is expected behavior.

You made a typo in the question I guess, since you should use `h` and `i` as functions:

``````cataTr f _ _ _ (Variable i) = f i
cataTr f g _ _ (Constant i) = g i
cataTr f g h i (Add e1 e2) = h (cataTr f g h i e1) (cataTr f g h i e2)
cataTr f g h i (Mul e1 e2) = i (cataTr f g h i e1) (cataTr f g h i e2)``````

or likely more elegant:

``````cataTr f g h i = go
where go (Variable i) = f i
go (Constant i) = g i
go (Add e1 e2) = h (go e1) (go e2)
go (Mul e1 e2) = i (go e1) (go e2)``````

or as @DanielWagner suggests, with a `case` expression:

``````cataTr f g h i = go
where go v = case v of
Variable i -> f i
Constant i -> g i
Add e1 e2 -> h (go e1) (go e2)
Mul e1 e2 -> i (go e1) (go e2)``````

Nevertheless, you can not call the function `cataTr` with `id` as third and fourth parameter. These functions require two parameters. Furthermore if `a` and `b` are different the two first parameters can not be both `id`, since your `f` maps an `a` to the result type, and the `g` maps a `b` to the result type.

You can for example pass the data constructor to construct an identity function with:

``cataTr Variable Constant Add Mul (Variable "X")``

this will thus yield `Variable "X"` again, or you can for example map all `Variable`s to `0` with `const 0`, and use `id`, `(+)` and `(*)` to evaluate an expression:

``cataTr (const 0) id (+) (*) (Variable "X")``