[Haskell-cafe] Transforming ASTs

Roman Cheplyaka roma at ro-che.info
Fri May 15 20:48:10 UTC 2015

On 15/05/15 19:08, anakreon wrote:
> 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.

As you say, you have something of type f a -> f a, but you need
something of type f a -> a to pass it to cata.

Or, more specifically (replacing f with BExpr and a with Expr), you have
something of type

  BExpr Expr -> BExpr Expr,

and you need something of type

  BExpr Expr -> Expr.

If only BExpr Expr was isomorphic to Expr!

Oh wait... it is. You define Expr as the fixpoint of BExpr, which means
that BExpr Expr and Expr are essentially the same.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150515/1447b18d/attachment.sig>

More information about the Haskell-Cafe mailing list