CODEWITHSUNDEEP
haskell
svr
svr

Reputation: 137

AST conversion in Haskell

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?

Upvotes: 5

Views: 344

Answers (1)

Toxaris
Toxaris

Reputation: 7276

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.

Upvotes: 2

Related Questions