Wie kann ich foldr in Form von foldMap für typenabgestimmte Sequenzen ausdrücken?

Question

Ich spiele mit type-aligned sequences herum, und insbesondere bin ich damit beschäftigt, sie zu falten. Ein faltbarer Typ ausrichte Sequenz sieht wie folgt aus etwas:

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

Es ist ziemlich einfach foldrTA in Bezug auf foldMapTA zu implementieren, indem zuerst foldMapTA unter Verwendung der Sequenz auf eine Art ausgerichtet Liste in der naiven Art und Weise (dh unter Verwendung zu konvertieren die Typ-ausgerichtete List-Kategorie) und falten dann über diese Liste. Leider kann dies ziemlich ineffizient sein, da lange Listen zu kurzen vorangestellt werden können. Ich habe versucht, einen Weg zu finden, einen Trick ähnlich dem in Data.Foldable zu verwenden, um die rechten und linken Falten effizienter zu definieren, aber die Typen machen mich schwindlig. Endo scheint nicht allgemein genug, um den Trick zu tun, und jeder Schritt, den ich in andere Richtungen nehme, führt mich zu mehr Typvariablen, als ich verfolgen kann.

Answer 1

fand ich, dass diese 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) 

Keine Ahnung, ob es Sinn macht, aber mit so vielen Typ-Indizes um, ich bezweifle, dass es viel Typ-checking Code ist, tut nicht Sinn .