对于具有嵌套 Maybe 值的 Tree 数据类型，Traversable 实例应该是什么样的？

Question

三天后我有一个 Haskell 考试，所以我想我应该稍微练习一下，然后调出过去的考试，其中一个具有以下树数据类型：

data Tree a = Leaf1 a | Leaf2 a a | Node (Tree a) (Maybe (Tree a)) deriving (Eq, Ord, Show)

起初看起来并没有那么有挑战性，但后来我意识到我必须为这棵树编写一个 Traversable 实例。处理树叶很容易：

instance Traversable Tree where
  traverse f (Leaf1 a)   = Leaf1 <$> f a
  traverse f (Leaf2 a b) = Leaf2 <$> f a <*> f b

但是，我开始运行遇到节点问题。

  traverse f (Node t Nothing)  = Node <$> traverse f t <*> Nothing
  traverse f (Node l (Just r)) = Node <$> traverse f l <*> Just (traverse f r)

当然，这些都行不通，我无法理解第二个 <*> 之后应该发生什么。我尝试使用漏洞，但 ghci 给我的消息并没有太大帮助（我知道问题出在类型上，但我不知道我应该如何解决它）。

这是我在尝试编译时收到的错误消息：

* Couldn't match type `f' with `Maybe'
  `f' is a rigid type variable bound by
    the type signature for:
      traverse :: forall (f :: * -> *) a b.
                  Applicative f =>
                  (a -> f b) -> Tree a -> f (Tree b)
    at exam.hs:92:3-10
  Expected type: f (Maybe (Tree b))
    Actual type: Maybe (Maybe (Tree b))
* In the second argument of `(<*>)', namely `Nothing'
  In the expression: Node <$> traverse f t <*> Nothing
  In an equation for `traverse':
      traverse f (Node t Nothing) = Node <$> traverse f t <*> Nothing
* Relevant bindings include
    f :: a -> f b (bound at exam.hs:94:12)
    traverse :: (a -> f b) -> Tree a -> f (Tree b)
      (bound at exam.hs:92:3)
   |
94 |   traverse f (Node t Nothing)  = Node <$> traverse f t <*> Nothing
   |                                                            ^^^^^^^

有人可以给我一些建议或解决此问题的方法吗？

Answer 1

traverse 允许您将 "function with an effect" 应用于数据结构的每个 "slot"，同时保持结构的形状。它具有以下类型：

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

它主要依赖于 "effects" 的类型是 Applicative 这一事实。 Applicatve提供了哪些操作？

它让我们可以提升纯函数并将它们应用到具有 <$> 的有效操作中。
它让我们可以将有效的操作与 (<*>) :: f (a -> b) -> f a -> f b 结合起来。注意第二个参数是一个有效的动作，不是一个纯值。
它让我们可以使用 pure :: a -> f a.

现在，节点有Nothing时，因为没有任何值，所以没有执行任何效果，但是<*>仍然需要在右侧执行有效操作。我们可以使用 pure Nothing 使类型适合。

当节点有一个 Just t 时，我们可以 traverse 类型 Tree a 的子树 t 与函数 a -> f b 并最终得到一个动作 f (Tree b)。但是 <*> 实际上期待 f (Maybe (Tree b))。提升的 Node 构造函数让我们期待这一点。我们可以做什么？

解决方案是使用 <$> 将 Just 构造函数提升到操作中，这是 fmap 的另一个名称。

请注意，我们没有更改值的整体 "shape"：Nothing 仍然是 Nothing，Just 仍然是 Just .子树的结构也没有改变：我们 traverse 递归地处理它们，但没有修改它们。

Answer 2

简而言之，您需要使用 traverse 才能进入 Maybe。

类型的 Traversable 和 Foldable 实例通常与其 Functor 实例具有相似的结构。而 fmap 将纯函数映射到结构上，将结果与纯构造函数组合起来：

instance Functor Tree where
  fmap f (Leaf1 a) = Leaf1 (f a)
  fmap f (Leaf2 a1 a2) = Leaf2 (f a1) (f a2)
  fmap f (Node ta mta) = Node (fmap f ta) (fmap (fmap f) mta)

注意 (fmap (fmap f) mta)：外部 fmap 映射到 Maybe，而内部 Tree 映射：

(fmap
  :: (Tree a -> Tree b)
  -> Maybe (Tree a) -> Maybe (Tree b))
  ((fmap
    :: (a -> b)
    -> Tree a -> Tree b)
    f)
  mta

traverse 而是在结构上映射一个有效的函数，并相应地将构造函数提升到 Applicative 与 <$> 和 <*> 运算符：

instance Traversable Tree where
  traverse f (Leaf1 a) = Leaf1 <$> f a
  traverse f (Leaf2 a1 a2) = Leaf2 <$> f a1 <*> f a2
  traverse f (Node ta mta) = Node <$> traverse f ta <*> traverse (traverse f) mta

再次注意，我们必须 traverse Maybe，并且在其中 traverse Tree，而不是纯函数 a -> b ，我们只有一个有效的函数 a -> f b，给定 Applicative f:

(traverse
  :: (Tree a -> f (Tree b))
  -> Maybe (Tree a) -> f (Maybe (Tree b)))
  ((traverse
    :: (a -> f b)
    -> Tree a -> f (Tree b))
    f)
  mta

同样，foldMap 具有类似的结构，但它不是重建数据类型，而是使用 Monoid 实例组合结果：

instance Foldable Tree where
  foldMap f (Leaf1 a) = f a
  foldMap f (Leaf2 a1 a2) = f a1 <> f a2
  foldMap f (Node ta mta) = foldMap f ta <> foldMap (foldMap f) mta

下面是 traverse 的简单用法示例：

> traverse (\ x -> print x *> pure (x + 1)) (Node (Leaf1 10) (Just (Leaf2 20 30)))
10
20
30
Node (Leaf1 11) (Just (Leaf2 21 31))

使用 DeriveFoldable、DeriveFunctor 和 DeriveTraversable 扩展，您可以向数据类型添加 deriving (Foldable, Functor, Traversable) 子句并使用 -ddump-deriv 标志GHC 查看生成的代码。

对于具有嵌套 Maybe 值的 Tree 数据类型，Traversable 实例应该是什么样的？

What should a Traversable instance look like for a Tree datatype with a nested Maybe value?

tree

haskell

maybe

traversable