折叠器的相同融合法可以应用于foldlmap吗？

Question

我已经读过没有foldl单独的融合法.如果我猜对了,这是由于foldl实施地图的尴尬 - 这主要是由于(foldl cons nil xs)反转列表.

如果我们使用conc列表,那么foldlmap这个方面的功能要好得多:

(foldlmap list conc nil xs) -> xs

如果我的猜测是正确的,那么应该有一个简单的融合法foldlmap.它是否正确？

Answer 1

我们可以从显式连接列表类型的"自然"折叠构建融合规则开始:

{-# LANGUAGE RankNTypes #-}

data ConcList a = List a | Conc (ConcList a) (ConcList a) | Nil

buildCL :: (forall l . (a -> l) -> (l -> l -> l) -> l -> l) -> ConcList a
buildCL g = g List Conc Nil

foldCL :: (a -> v) -> (v -> v -> v) -> v -> ConcList a -> v
foldCL list conc nil cl = go cl
   where
      go (List a) = list a
      go (Conc cl1 cl2) = conc (go cl1) (go cl2)
      go Nil = nil

{-# RULES "foldCL/buildCL"
      forall list conc nil
             (g :: (forall l . (a -> l) -> (l -> l -> l) -> l -> l))
         . foldCL list conc nil (buildCL g) = g list conc nil #-}

然后在理论上这转化为相当于"正常"的列表:

buildCL2 :: (forall l . (a -> l) -> (l -> l -> l) -> l -> l) -> [a]
buildCL2 g = g (\a -> [a]) (++) []

{-# RULES "foldl/map/buildCL2"
      forall list conc nil
             (g :: (forall l . (a -> l) -> (l -> l -> l) -> l -> l))
         . foldl conc nil (map list (buildCL2 g)) = g list conc nil #-}

但是foldr/build列表的美妙之处在于它适用于很多东西,因为许多功能都是"自然生产者"(可以根据其重写build)而且很多都是自然消费者(可以根据其重写foldr).我认为这种模式foldl/map/buildCL2要难以设计.