haskellcatamorphism# 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")`

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code