Traversable is to Applicative contexts 是什么意思？

Question

我试图在 https://namc.in/2018-02-05-foldables-traversals 的帮助下理解 Traversable。

作者某处提到了下面这句话：

Traversable is to Applicative contexts what Foldable is to Monoid values.

他试图澄清什么？

我不明白 Foldable to Monoid 之间的联系。

请举例。

Answer 1

一开始是foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b

还有 mapM:

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

foldr 通过让每种类型定义自己的 foldr 定义来描述如何将其缩减为单个值，从而将 [a] 推广到 [a] 以外的数据类型。

-- old foldr ::        (a -> b -> b) -> b -> [] a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t  a -> b

如果你有一个幺半群，你不必指定二元函数，因为 Monoid 实例已经提供了它自己的起始值并且知道如何组合两个值，这从它的默认值中是显而易见的根据 foldr:

定义

-- If m is a monoid, it provides its own function of type b -> b.
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty

Traverse 从列表到可遍历类型进行相同类型的泛化，但对于 mapM:

-- old mapM ::              Monad m        => (a -> m b) -> [] a -> m ([] b)
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t  a -> f (t  b)

(当 mapM 第一次定义时，没有 Applicative class；如果有，可以定义 mapA :: Applicative f => (a -> f b) -> [a] -> f [b]；Monad 约束比必要的强。）

Applicative 本质上是幺半群的，因此 Traverse 中不需要 foldr/foldMap 绘制的区分类型。

Answer 2

这篇文章（the corresponding passage of the Wikibook) is talking about how the effects (or, to use the language seen there, the contexts) of applicative values can be combined monoidally. The connection with Foldable is that list-like folding is ultimately amounts to combining values monoidally (see , and also Foldr/Foldl for free when Tree is implementing Foldable foldmap?. As for the applicative contexts part, there are a few ways to look at that. One of them is noting that, for any Applicative f and Monoid m, f m is a monoid, with pure mempty as mempty and liftA2 mappend as mappend (this Ap type from the reducers package 见证了这一点）。举个具体的例子，我们选择 f ~ Maybe 和 m ~ ()。这给我们留下了四种可能的组合：

liftA2 mappend (Just ()) (Just ()) = Just ()
liftA2 mappend (Just ()) Nothing   = Nothing
liftA2 mappend Nothing   (Just ()) = Nothing
liftA2 mappend Nothing   Nothing   = Nothing

现在与 All 对比，Bool 幺半群与 (&&) 为 mappend:

mappend (All True)  (All True)  = All True
mappend (All True)  (All False) = All False
mappend (All False) (All True)  = All False
mappend (All False) (All False) = All False

它们完美匹配：Just () 代表 True，Nothing 代表 False，liftA2 mappend 代表 (&&)。

现在让我们再看一下 Wikibook 示例：

deleteIfNegative :: (Num a, Ord a) => a -> Maybe a
deleteIfNegative x = if x < 0 then Nothing else Just x

rejectWithNegatives :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
rejectWithNegatives = traverse deleteIfNegative

GHCi> rejectWithNegatives [2,4,8]
Just [2,4,8]
GHCi> rejectWithNegatives [2,-4,8]
Nothing

通过将 deleteIfNegative 应用于列表中的值生成的 Maybe 值按上面显示的方式单向组合，因此我们得到 Nothing 除非 all Maybe 值是 Just.

这件事也可以反着来。通过 Applicative 实例 Const...

-- I have suppressed a few implementation details from the instance used by GHC.
instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

...我们可以从任何 Monoid 中得到一个 Applicative，这样 (<*>) 单向地组合幺半群值。这使得 define foldMap and friends in terms of traverse.

成为可能

最后一点，Applicative 作为幺半群仿函数的 class 的范畴理论描述与我在此处介绍的内容有很大不同。有关此问题和其他细则的进一步讨论，请参阅（如果您想深入挖掘，阅读那里的所有答案是非常值得的）。

Traversable is to Applicative contexts 是什么意思？

What does Traversable is to Applicative contexts mean?

haskell

applicative

monoids

traversable

foldable