AST conversion in Haskell

Question

I've an AST whose root node is of type E.Root. I need to convert it into an AST with root node whose type is I.Root.

I can now define a function eToI with type signature :

eToI :: E.Root -> AdditionalInfo -> I.Root

However, both the ASTs share a lot of nodes. So, the function eToF has a lot of boilerplate code building I's nodes from E's nodes which are essentially the same.

I would like to solve these 2 problems :

1. At the type level, avoid defining the nodes of I. I have all the nodes of E defined. I define what nodes change in I. Can I have the compiler generate all the types in I, by somehow mapping what needs to change?

2. At the value level, I'd only want to define transformations for the nodes that change like (assuming E's A is mapped to I's Z ..) :

       aToZ :: E.A -> AdditionalInfo -> I.Z
       bToY :: E.B -> AdditionalInfo -> I.Y
   

   Now, can the compiler generate a function like eToI?

       eToI :: E.Root -> AdditionalInfo -> I.Root
   

What's Haskell's idiomatic approach to do this?

Answer 1

Sometimes you can factor out the common aspects of E.Root and I.Root into one ore more reusable datatypes. It usually also helps to hide the AdditionalInfo -> ... in a monad or an applicative functor. For example, here's some pseudocode:

module Common where
  {-# LANGUAGE DeriveTraversable #-}
  data Reusable root = ... root ...
    deriving (Functor, Foldable, Traversable)

module E where
  import Common
  data Root = Leaf (Reusable Root) | Node Root

module I where
  {-# LANGUAGE GeneralizedNewtypeDeriving #-}
  import Common

  import Data.Monoid

  data Root = Root [Reusable Root]
    deriving Monoid

module Transform where
  import Common
  import qualified E
  import qualified I

  import Control.Applicative
  import Control.Monad.Reader
  import Data.Monoid

  type AdditionalInput = ...
  type F = Reader AdditionalInput

  convertRoot :: E.Root -> F I.Root
  convertRoot (Leaf reusable) =
    traverse convertRoot reusable
  convertRoot (Node left right) =
    liftA2 mappend (convertRoot left) (convertRoot right)

Now I can use traverse to convert between Reusable E.Root and Reusable I.Root.