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.


  • 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")