Suppose the following data type for encoding Boolean expressions:

data BExpr a = BTrue | BFalse | Id String | Not a | And a a | Or a a | BEq a a deriving (Functor) type Expr = Fix BExpr

It is easy to produce a string representation of an expression or evaluate it:

estr :: BExpr String -> String eval :: BExpr Bool -> Bool

with the cata function from Data.Functor.Fixedpoint.

Could you suggest a solution for transforming trees encoded as Exp into equivalent Expr (e.g Not Not a ~> a)? cata does not work since it expects a function f a -> a while a transformation would be f a -> f a.

Actually cata works just fine, all you need following transformation which is f a -> a alg :: BExpr Expr -> Expr alg (Not (Fix (Not a))) = a alg x = Fix x