title: A simple compiler between two ASTs exposing identical language types and operations
body: <p>I'm looking for an elegant way to solve the problem below. All options are welcome, particularly type classes and GADTs :-)</p>
  
  <p>The scenario is this: there exists a small language with types (Strings and Ints) and operations (+, -, ++ and split). There are two syntax's for the language, each with their own parser. I'd like to write a compiler that can go either from language X to language Y, or from Y to X. Compiling from one to the other is a straight forward mapping over a list of expressions with one of these:</p>
  
  <pre><code>xToY :: ExpX -&gt; ExpY
  yToX :: ExpY -&gt; ExpX
  </code></pre>
  
  <p>.. followed by a <code>show</code> over either <code>[ExpY]</code> or <code>[ExpX]</code>. Here is a naive implementation of these two compiler functions, using normal data definitions and pattern matching on constructors:</p>
  
  <pre>
  {-# LANGUAGE LambdaCase #-}
  
  module Compiler where
  
  data ExpX = StringX String | IntX Int | ArithOpX ArithExpX | StringOpX StringExpX deriving (Show)
  data ArithExpX = EAddX ExpX ExpX | EMinusX ExpX ExpX deriving (Show)
  data StringExpX = EAppendX ExpX ExpX | ESplitX ExpX ExpX deriving (Show)
  
  data ExpY = StringY String | IntY Int | ArithOpY ArithExpY | StringOpY StringExpY deriving (Show)
  data ArithExpY = EAddY ExpY ExpY | EMinusY ExpY ExpY deriving (Show)
  data StringExpY = EAppendY ExpY ExpY | ESplitY ExpY ExpY deriving (Show)
  
  xToY :: ExpX -> ExpY
  xToY =
      \case
      StringX s -> StringY s
      IntX i -> IntY i
      ArithOpX (EAddX a b) -> ArithOpY (EAddY (xToY a) (xToY b))
      ArithOpX (EMinusX a b) -> ArithOpY (EMinusY (xToY a) (xToY b))
      StringOpX (EAppendX a b) -> StringOpY (EAppendY (xToY a) (xToY b))
      StringOpX (ESplitX a b) -> StringOpY (ESplitY (xToY a) (xToY b))
  
  yToX :: ExpY -> ExpX
  yToX =
      \case
      StringY s -> StringX s
      IntY i -> IntX i
      ArithOpY (EAddY a b) -> ArithOpX (EAddX (yToX a) (yToX b))
      ArithOpY (EMinusY a b) -> ArithOpX (EMinusX (yToX a) (yToX b))
      StringOpY (EAppendY a b) -> StringOpX (EAppendX (yToX a) (yToX b))
      StringOpY (ESplitY a b) -> StringOpX (ESplitX (yToX a) (yToX b))
  </pre>
  
  <p>Testing the noddy compiler:</p>
  
  <pre>
  *Compiler> xToY (ArithOpX (EAddX (IntX 2) (IntX 5)))
  ArithOpY (EAddY (IntY 2) (IntY 5))
  *Compiler> yToX (StringOpY (ESplitY (StringY "foo") (StringY "bar")))
  StringOpX (ESplitX (StringX "foo") (StringX "bar"))
  </pre>
  
  <p>So it works. Unfortunately, there is a lot code repetition and a pattern is clearly emerging. I'd like to adopt a more elegant feature of Haskell to achieve the same result given by <code>xToY</code> and <code>yToX</code>. In particular, I'm looking for a way to define duality between constructors, for example <code>StringX s</code> gets compiled to <code>StringY s</code> whilst <code>StringY s</code> gets compiled back in to <code>StringX s</code>. Surely there's a nice way to express this? Moreover, the nested <code>xToY</code> and <code>yToX</code> calls on the right side of the case matching looks grungy, e.g. <code>ArithOpX (EAddX (yToX a) (yToX b))</code>. There must be a better way?</p>