如果我正确理解您的示例,则类型为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
距离Data.Foldable
的foldMap
专业化,因此在现实中,我们不需要去定义它,我们就可以导入它的更一般的版本:
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,这是这些想法进一步阐述。
我认为有一个解决方案使用Arrow的***和&&&,使用像(f,(g,(h,i)))而不是(f,g,h,i)在引擎盖下的类型,现在距离我的笔记本电脑几百英里远,所以今天不能玩。 – AndrewC 2014-09-26 23:32:36