title: How can I express foldr in terms of foldMap for type-aligned sequences?
body: <p>I'm playing around with <a href="https://hackage.haskell.org/package/type-aligned-0.9.6/docs/Data-TASequence.html">type-aligned sequences</a>, and in particular I'm messing around with the idea of folding them. A foldable type-aligned sequence looks something like this:</p>
  
  <pre><code>class FoldableTA fm where
    foldMapTA :: Category h =&gt;
                  (forall b c . a b c -&gt; h b c) -&gt;
                  fm a b d -&gt; h b d
    foldrTA :: (forall b c d . a c d -&gt; h b c -&gt; h b d) -&gt;
               h p q -&gt; fm a q r -&gt; h p r
    foldlTA :: ...
  </code></pre>
  
  <p>It's pretty easy to implement <code>foldrTA</code> in terms of <code>foldMapTA</code> by first using <code>foldMapTA</code> to convert the sequence to a type-aligned list in the naive way (i.e., using the type-aligned list category) and then folding over that list. Unfortunately, this can be quite inefficient because long lists may be prepended to short ones. I've been trying to figure out a way to use a trick similar to the one used in <code>Data.Foldable</code> to define the right and left folds more efficiently, but the types are making me dizzy. <code>Endo</code> does not seem general enough to do the trick, and every step I take in other directions leads me to more type variables than I can keep track of.</p>