Implementing a catamorphism for Expression Trees

Question

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.

Answer 1

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 Variables to 0 with const 0, and use id, (+) and (*) to evaluate an expression:

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