11

三天后我有一个 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
   |                                                            ^^^^^^^

有人可以给我一些指示或解决此问题的可能吗？

4

2 回答 2

7

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.

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

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

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

请注意，我们没有改变值的整体“形状”：Nothingis still Nothing， the Justis still Just。子树的结构也没有改变：我们traverse递归地处理它们，但没有以其他方式修改它们。

于 2020-06-01T17:24:12.433 回答
7

简短的回答是您需要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

traverseApplicative而是在结构上映射一个有效的函数，并使用<$>and运算符相应地将构造函数提升为<*>：

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-derivGHC 的标志来查看生成的代码。

于 2020-06-01T17:29:53.677 回答