title: How to define fmap in a GADT Expression?
body: <p>Given a simple "language":</p>
  
  <pre><code>data Expr a where
    ConstE   :: a                  -&gt; Expr a
    FMapE    :: (b -&gt; a) -&gt; Expr b -&gt; Expr a
  
  instance Functor Expr where
      fmap = FMapE
  
  interpret :: Expr a -&gt; a
  interpret (ConstE a) = a
  interpret (FMapE f a) = f (interpret a)
  </code></pre>
  
  <p>From that I would like to extract a call graph, eg:</p>
  
  <pre><code>foo = fmap show . fmap (*2) $ ConstE 1
  </code></pre>
  
  <p>Should result in the graph <code>Node 1 -&gt; Node (*2) -&gt; Node show</code>. Ideally I'd like to store this in a <code>Data.Graph</code>.</p>
  
  <hr>
  
  <p>What I've come up to this point is that it should be possible to use <code>System.Mem.StableNames</code> to identify individual nodes and store them in a <code>HashMap (StableName (Expr a)) (Expr a)</code>. </p>
  
  <pre><code>toHashMap :: Expr a -&gt; HashMap (StableName (Expr a)) (Expr a)
  toHashMap n@ConstE = do
      sn &lt;- makeStableName n
      return $ HashMap.singleton sn n
  </code></pre>
  
  <p>The problem is, that there seems to be no way to get through the <code>FMapE</code> nodes:</p>
  
  <pre><code>toHashMap n@(FMapE _ a) = do
      snN &lt;- makeStableName n
      snA &lt;- makeStableName a
      -- recurse
      hmA &lt;- toHashMap a
      -- combine
      return $ HashMap.singleton snN n `HashMap.union` hmA
  </code></pre>
  
  <hr>
  
  <p>GHC will complain along the lines of this:</p>
  
  <pre><code>Couldn't match type ‘t’ with ‘b’
    because type variable ‘b’ would escape its scope
  This (rigid, skolem) type variable is bound by
    a pattern with constructor
      FMapE :: forall a b. (b -&gt; a) -&gt; Expr b -&gt; Expr a,
    in an equation for ‘toHashMap’
  </code></pre>
  
  <p>I can see that this won't match ... but I have no clue on how to make this work. </p>
  
  <hr>
  
  <h3>Edit</h3>
  
  <p>This probably boils down to writing a <code>children</code> function:</p>
  
  <pre><code>children :: Event a -&gt; [Event a]
  children (ConstE)    = []
  children (FMapE _ a) = [a] -- doesn't match ...
  </code></pre>
  
  <p>For the same reason I can't uniplate on this ...</p>