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

Question

三天后我有一个 Haskell 考试，所以我想我应该练习一下并提取过去的考试，其中一个具有以下 Tree 数据类型：

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

但是，我开始遇到 Node.js 的问题。

  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允许您将“具有效果的函数”应用于数据结构的每个“槽”，保持结构的形状。它有以下类型：

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

它主要依赖于这样一个事实，即“效果”的类型是Applicative. Applicatve提供什么操作？

• 它让我们提升纯函数并将它们应用到有效的操作中<$>。
• 它让我们将有效的操作与(<*>) :: f (a -> b) -> f a -> f b. 请注意，第二个参数是一个有效的操作，而不是一个纯粹的值。
• 它让我们可以使用任何纯值并将其置于有效的上下文中，使用pure :: a -> f a.

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

当节点有 a 时Just t，我们可以用函数生成 typetraverse的子树t，并以一个 action 结束。但实际上是在期待一个. 提升的构造函数让我们期待。我们可以做什么？Tree aa -> f bf (Tree b)<*>f (Maybe (Tree b))Node

解决方案是使用 将Just构造函数提升到操作中<$>，这是fmap.

请注意，我们并没有改变整体的“形”的价值：在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代替映射在该结构上的功能effectful，并且相应地提起构造成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，我们只需要一个effectful功能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-derivGHC的标志，以查看生成的代码。