title: Fold over a heterogeneous, compile time, list
body: <p>I have a list of heterogeneous types (or at least that's what I have in mind):</p>
  
  <pre><code>data Nul
  
  data Bits b otherBits where 
      BitsLst :: b -&gt; otherBits -&gt; Bits b otherBits 
      NoMoreBits :: Bits b Nul
  </code></pre>
  
  <p>Now, given an input type <code>b</code>, I want to go through all the slabs of <code>Bits</code> with type <code>b</code> and summarize them, ignoring other slabs with type <code>b' /= b</code>:</p>
  
  <pre><code>class Monoid r =&gt; EncodeBit b r | b -&gt; r where 
      encodeBit :: b -&gt; r
  
  class AbstractFoldable aMulti r where 
      manyFold :: r -&gt; aMulti -&gt; r
  
  instance (EncodeBit b r, AbstractFoldable otherBits r) =&gt; 
                       AbstractFoldable (Bits b otherBits ) r where 
      manyFold r0 (BitsLst bi other) = manyFold (r0 `mappend` (encodeBit bi)) other
      manyFold b0 NoMoreBits = b0 
  
  instance AbstractFoldable otherBits r =&gt;
                       AbstractFoldable (Bits nb    otherBits ) r where 
      manyFold r0 (BitsLst _ other) = manyFold r0 other
      manyFold b0 NoMoreBits = b0 
  </code></pre>
  
  <p>But the compiler wants none of it. And with good reason, since both instance declarations have the same head. Question: what is the correct way of folding over <code>Bits</code> with an arbitrary type?</p>
  
  <p>Note: the above example is compiled with </p>
  
  <pre><code>{-# LANGUAGE MultiParamTypeClasses, 
               FunctionalDependencies,
               GADTs,
               DataKinds,
               FlexibleInstances,
               FlexibleContexts
  #-}
  </code></pre>