如何实现遍历使用foldMap

Question

foldMap可以通过遍历实现:

foldMap f = getConst . traverse (Const . f)

所以,我的问题是如何通过foldMap实现遍历:

traverse f = ...

要么

it Can't be accomplished ?

Answer 1

有些Foldable情况无法完成.

data Blonk a = Blink | Blank

instance Functor Blonk where
    fmap f Blink = Blink
    fmap f Blank = Blank

instance Foldable Blonk where
    foldMap f _ = mempty

以上是唯一可能的总,守法的实现Functor和Foldable对Blonk.现在有一条法律Traversable:

traverse Identity = Identity

让我们看看它是如何发挥作用的,假设是以某些术语traverse来实现的foldMap,也就是说,有一些术语g和h(f如果他们喜欢的话可能会提到):

traverse f = g . foldMap h

然后:

traverse f x = g (foldMap h x)
             = g mempty
-- THEREFORE
traverse Identity x = g mempty

注意,g mempty不依赖于x,因此必须是Identity Blink或Identity Blank适合该类型.在前一种情况下,

traverse Identity Blank = Identity Blink
                       != Identity Blank

并违反了法律.同样traverse Identity Blink是证人在另一案件中违反了法律.

(并且,为了证明我没有任何打击,有一个守法的Traversable例子:

instance Traversable Blonk where
    traverse f Blink = pure Blink
    traverse f Blank = pure Blank

)