Как я могу выразить foldr в терминах foldMap для последовательностей, выровненных по типу?

Question

Я играю с type-aligned sequences, и, в частности, я возился с идеей складывания их. Складная последовательность типа выровнено выглядит примерно так:

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 :: ... 

Это довольно легко реализовать foldrTA с точкой зрения foldMapTA сначала с помощью foldMapTA, чтобы преобразовать последовательность в список типа выровненных в наивном способе (то есть, используя тип списка с выравниванием по типу), а затем складывается над этим списком. К сожалению, это может быть весьма неэффективным, поскольку длинные списки могут быть добавлены к коротким. Я пытаюсь найти способ использовать трюк, подобный тому, который используется в Data.Foldable, чтобы определить правильную и левую складки более эффективно, но типы заставляют меня головокружение. Endo не кажется достаточно общим, чтобы сделать трюк, и каждый шаг, который я предпринимаю в других направлениях, приводит меня к большему количеству переменных типа, которые я могу отслеживать.

Answer 1

Я обнаружил, что это 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) 

Не знаю, если это имеет смысл, но с таким количеством индексов типа вокруг, я сомневаюсь, что есть много проверок типов кода, который делает не имеет смысл ,