如何根据类型对齐的序列的foldMap表达foldr？ [英] How can I express foldr in terms of foldMap for type-aligned sequences?

问题描述

我正在玩弄类型对齐的序列，特别是我搞乱折叠它们的想法。一个可折叠的类型对齐的序列看起来像这样：

I'm playing around with type-aligned sequences, and in particular I'm messing around with the idea of folding them. A foldable type-aligned sequence looks something like this:

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 将序列转换为一个类型，以 foldMapTA 的形式> foldrTA 对齐的列表以天真的方式（即，使用类型对齐的列表类别），然后折叠该列表。不幸的是，这可能是非常低效的，因为长列表可能会被列为短列表。我一直试图找出一种方法来使用类似于 Data.Foldable 中使用的技巧来更有效地定义右侧和左侧折叠，但类型是让我头晕。 Endo 看起来不够普遍，我在其他方向上的每一步都会导致我获得更多的类型变量，而不是我可以跟踪的。

It's pretty easy to implement foldrTA in terms of foldMapTA by first using foldMapTA 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 Data.Foldable to define the right and left folds more efficiently, but the types are making me dizzy. Endo 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.

推荐答案

我发现这个类型：

I found that this 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)

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

No idea if it makes any sense, but with so many type indexes around, I doubt that there is much type-checking code that does not make sense.

这篇关于如何根据类型对齐的序列的foldMap表达foldr？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！