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.