8

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

作者在某处提到了以下句子：

Traversable 对于 Applicative 上下文就像 Foldable 对于 Monoid 值一样。

他试图澄清什么？

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

请举个例子。

4

2 回答 2

9

一开始，有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实例已经提供了它自己的起始值并且知道如何组合两个值，这从它的默认定义中可以明显看出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约束比必要的要强。）

AnApplicative本质上是幺半群，因此不需要/绘制Traverse的区分类型。foldrfoldMap

于 2019-04-05T12:41:18.457 回答
0

这篇文章（以及Wikibook 的相应段落）正在讨论如何将应用值的效果（或者，使用那里看到的语言，上下文）组合成幺半群。与Foldable类似列表的折叠最终相当于单向组合值（参见chepner 的答案，以及当 Tree 实现可折叠折叠图时免费的 Foldr/Foldl？。至于应用上下文部分，有几种方法可以查看其中一个注意到，对于任何Applicative fand Monoid m，f m是一个幺半群，带有pure memptyasmempty和liftA2 mappendas mappend(这种Ap类型来自reducers包见证）。举个具体的例子，让我们选择f ~ Maybe和m ~ ()。这给我们留下了四种可能的组合：

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

现在对比，与asAll的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、NothingforFalse和liftA2 mappendfor (&&)。

现在让我们再看一下 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的值以上面显示的方式进行单曲面组合，因此我们得到 a ，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从 any中得到一个Monoid，这样就可以(<*>)将 monoidal 值组合在一起。这使得定义foldMap和朋友traverse成为可能。

最后一点，作为幺半群函子的类的范畴理论描述Applicative涉及与我在这里讨论的完全不同的东西。有关此问题和其他细则的进一步讨论，请参阅Monoidal Functor is Applicative 但是 Applicative 定义中的 Monoid 类型类在哪里？（如果你想更深入地挖掘，阅读那里的所有答案是非常值得的）。

于 2019-04-06T00:01:25.773 回答