haskell - 使用通用元组函数一次多次折叠

Question

如何编写一个函数，该函数采用 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 扩展没问题。

Answer 1

如果我正确理解您的示例，则类型为 ai -> b -> ai ，而不是 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)

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

第四次观察:What are folds made of?答:folds are made of monoids!

import Data.Monoid

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

这个fold只是 foldMap 的特化来自 Data.Foldable ，所以实际上我们不需要定义它，我们可以只导入它更通用的版本:

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

如果您 fold与 Endo ，这与从右侧折叠相同。要从左边折叠，你想用 Dual (Endo r) 折叠。单体:

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)

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

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

也值得一看:Composable Streaming Folds ，这是对这些想法的进一步阐述。