haskell - 对于具有嵌套 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使类型适合。

当节点有 Just t ，我们可以traverse子树 t类型 Tree a使用函数 a -> f b并以一个 Action 结束f (Tree b) .但是 <*>实际上期待 f (Maybe (Tree b)) .解除Node构造函数让我们期待。我们能做什么？

解决办法是解除Just构造函数使用 <$> ，这是 fmap 的另一个名称.

请注意，我们没有更改值的整体“形状”:Nothing仍然是 Nothing , Just仍然是 Just .子树的结构也没有改变:我们 traverse d 他们递归，但没有以其他方式修改它们。