This might be a duplicated message. The first time I posted it I had not subscribed to haskell cafe. 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.