Jak mogę wyrazić foldr w kategoriach foldMap dla sekwencji wyrównanych do typu?

Question

Gram w pobliżu z type-aligned sequences, a zwłaszcza mam problem z ich złożeniem. Składany sekwencją typu wyrównany wygląda mniej więcej tak:

class FoldableTA fm where 
    foldMapTA :: Category h => 
       (forall b c . a b c -> h b c) -> 
       fm a b d -> h b d 
    foldrTA :: (forall b c d . a c d -> h b c -> h b d) -> 
      h p q -> fm a q r -> h p r 
    foldlTA :: ... 

Jest to dość łatwe do wdrożenia foldrTA pod względem foldMapTA najpierw za pomocą foldMapTA przekonwertować sekwencję na liście typów wyrównany w naiwny sposób (czyli, używając kategorią list wyrównanych do typu), a następnie składaną na tej liście. Niestety może to być dość nieefektywne, ponieważ długie listy mogą być poprzedzone krótkimi. Próbowałem znaleźć sposób na użycie sztuczki podobnej do tej użytej w Data.Foldable, aby efektywniej zdefiniować prawą i lewą fałdę, ale typy powodują, że mam zawroty głowy. Endo nie wydaje się być na tyle ogólny, aby zrobić lewę, a każdy krok, który podejmuję w innych kierunkach, prowadzi mnie do większej liczby zmiennych, niż mogę śledzić.

Answer 1

Okazało się, że to typechecks:

{-# LANGUAGE RankNTypes #-} 
module FoldableTA where 

import Control.Category 
import Prelude hiding (id, (.)) 

class FoldableTA fm where 
    foldMapTA :: Category h => (forall b c . a b c -> h b c) -> fm a b d -> h b d 
    foldrTA :: (forall b c d . a c d -> h b c -> h b d) -> h p q -> fm a q r -> h p r 
    foldrTA f z t = appEndoTA (foldMapTA (\x -> TAEndo (f x)) t) z 

newtype TAEndo h c d = TAEndo { appEndoTA :: forall b. h b c -> h b d } 

instance Category (TAEndo h) where 
    id = TAEndo id 
    TAEndo f1 . TAEndo f2 = TAEndo (f1 . f2) 

Nie mam pojęcia, czy to ma jakiś sens, ale z tak wieloma indeksami typu całego wątpię, że istnieje wiele kod typu sprawdzając, czy nie sens .