Traversable对应用语境的意义是什么？

Question

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

在某处提交人提到了以下句子：

可遍历的是适用于Foidable对Monoid值的上下文。

他试图澄清什么？

我没有得到Foldable to Monoid之间的联系。

请举个例子。

Answer 1

一开始，有foldr：

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

并且有mapM：

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

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

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

如果你有一个monoid，你不必指定一个二元函数，因为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类;如果有，则可以定义mapA :: Applicative f => (a -> f b) -> [a] -> f [b]; Monad约束强于必要。）

Applicative本质上是幺半群的，所以Traverse没有必要为foldr / foldMap绘制的区分类型。

Answer 2

文章（和the corresponding passage of the Wikibook）正在谈论如何将应用价值的影响（或者，使用在那里看到的语言，情境）单一地结合起来。与Foldable的关系是类似列表的折叠最终等于单一地组合值（参见chepner's answer，以及Foldr/Foldl for free when Tree is implementing Foldable foldmap?。至于适用的上下文部分，有几种方法可以看待它。其中一个注意到，因为任何Applicative f和Monoid m，f m是一个幺半群，pure mempty为mempty，liftA2 mappend为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 monoid与(&&)作为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

通过将Maybe应用于列表中的值而生成的deleteIfNegative值以上面所示的方式单独组合，因此除非所有Nothing值都是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)

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

最后一点，Applicative作为幺半群仿函数的类别理论描述涉及的内容与我在此处所涉及的内容有很大不同。有关此问题以及其他细则的进一步讨论，请参阅Monoidal Functor is Applicative but where is the Monoid typeclass in the definition of Applicative?（如果您想深入挖掘，那么阅读那里的所有答案是非常值得的）。