[Haskell-cafe] Haskell-Cafe Digest, Vol 141, Issue 25

[Michael Baikov]

>
> 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