haskell - 使用通用元组功能一次通过多次折叠

如何编写一个函数，该函数采用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，而不是您最初编写的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形式的类型有时称为内同态，并且这些类型中的每一个都具有一个monoid，其组成为关联操作，而identity功能为identity。 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)

第三个观察结果:两个monoid的乘积也是一个monoid，根据此实例，也来自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) 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)

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

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

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

关于haskell - 使用通用元组功能一次通过多次折叠，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26050428/

AI

haskell - 使用通用元组功能一次通过多次折叠