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

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

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 не кажется достаточно общим, чтобы сделать трюк, и каждый шаг, который я делаю в других направлениях, приводит меня к большему количеству переменных типа, которые я могу отслеживать.

Ответы

Ответ 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)

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