haskell - 如何使用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

以上是 Blonk 的 Functor 和 Foldable 唯一可能的完整、守法的实现。现在有一条关于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

)