我如何根据类型对齐序列的 foldMap 来表达 foldr？

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

通过首先使用 foldMapTA 以天真的方式将序列转换为类型对齐列表（即使用类型对齐的列表类别），然后折叠该列表。不幸的是，这可能效率很低，因为长列表可能会放在短列表之前。我一直在尝试找出一种方法来使用类似于 Data.Foldable 中使用的技巧来更有效地定义左右折叠，但类型让我头晕。 Endo 似乎不够通用，无法做到这一点，我在其他方向上采取的每一步都会让我得到更多的类型变量，而我无法跟踪。

Answer 1

我发现这个类型检查：

{-# 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)

不知道它是否有意义，但是有这么多类型索引，我怀疑是否有很多类型检查代码 not 有意义。

我如何根据类型对齐序列的 foldMap 来表达 foldr？

How can I express foldr in terms of foldMap for type-aligned sequences?

haskell

types

monoids

type-variables

foldable