使用通用元组函数一次进行多次折叠

如何编写一个接受类型函数元组的函数ai -> b -> ai并返回一个函数，该函数接受类型元素的元组ai, 类型的一个元素b，并将每个元素组合成一个新的元组ai:

那是签名应该是这样的

f :: (a1 -> b -> a1, a2 -> b -> a2, ... , an -> b -> an) -> 
     (a1, a2, ... , an) -> 
     b -> 
     (a1, a2, ... , an)

这样：

f (min, max, (+), (*)) (1,2,3,4) 5 = (1, 5, 8, 20) 

这样做的目的是让我可以写：

foldlMult' t = foldl' (f t)

然后做类似的事情：

foldlMult' (min, max, (+), (*)) (head x, head x, 0, 0) x 

一次完成多次折叠。 GHC 扩展没问题。

如果我理解你的例子正确的话，类型是ai -> b -> ai, not ai -> b -> a正如你第一次写的那样。让我们将类型重写为a -> ri -> ri，只是因为它帮助我思考。

首先要观察的是以下对应关系：

(a -> r1 -> r1, ..., a -> rn -> rn) ~ a -> (r1 -> r1, ..., rn -> rn)

这允许您编写这两个相反的函数：

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (r1 -> r1, r2 -> r2)
pullArg (f, g) = \a -> (f a, g a)

pushArg :: (a -> (r1 -> r1, r2 -> r2)) -> (a -> r1 -> r1, a -> r2 -> r2) 
pushArg f = (\a -> fst (f a), \a -> snd (f a))

第二个观察：表格的类型ri -> ri有时被称为自同态，并且每个类型都有一个幺半群，以组合作为结合运算，以恒等函数作为恒等。这Data.Monoid包中有这样的包装：

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
    mempty = id
    mappend = (.)

这允许您重写之前的pullArg对此：

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (Endo r1, Endo r2)
pullArg (f, g) = \a -> (Endo $ f a, Endo $ g a)

第三个观察：两个幺半群的乘积也是一个幺半群，根据这个例子也来自Data.Monoid:

instance (Monoid a, Monoid b) => Monoid (a, b) where
    mempty = (mempty, mempty)
    (a, b) `mappend` (c, d) = (a `mappend` c, b `mappend d)

对于任意数量参数的元组也是如此。

第四个观察：褶皱是由什么制成的？ http://web.jaguarpaw.co.uk/~tom/blog/posts/2012-11-04-what-is-foldr-made-of.html回答：折叠是由幺半群组成的！ http://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-monoids/

import Data.Monoid

fold :: Monoid m => (a -> m) -> [a] -> m
fold f = mconcat . map f

This fold只是一个专业化foldMap from Data.Foldable，所以实际上我们不需要定义它，我们可以导入它更通用的版本：

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

If you fold with Endo，这与从右侧折叠相同。要从左侧折叠，您需要用Dual (Endo r) monoid:

myfoldl :: (a -> Dual (Endo r)) -> r -> -> [a] -> r
myfoldl f z xs = appEndo (getDual (fold f xs)) z


-- From `Data.Monoid`.  This just flips the order of `mappend`.
newtype Dual m = Dual { getDual :: m }

instance Monoid m => Monoid (Dual m) where
    mempty = Dual mempty
    Dual a `mappend` Dual b = Dual $ b `mappend` a

记住我们的pullArg功能？让我们稍微修改一下，因为您是从左侧折叠的：

pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> Dual (Endo r1, Endo r2)
pullArg (f, g) = \a -> Dual (Endo $ f a, Endo $ g a)

我声称，这是你的 2 元组版本f，或者至少与其同构。您可以将折叠函数重构为以下形式a -> Endo ri，然后执行：

let (f'1, ..., f'n) = foldMap (pullArgn f1 ... fn) xs
in (f'1 z1, ..., f'n zn) 

还值得一看：可组合的流式折叠 http://www.haskellforall.com/2013/08/composable-streaming-folds.html，这是对这些想法的进一步阐述。