haskell - 有人能解释一下 Haskell 中的遍历函数吗？

Question

我正在尝试从 Data.Traversable 中理解 traverse 函数，但失败了。我看不出它的意义。由于我来自命令式背景，有人可以用命令式循环向我解释一下吗？伪代码将不胜感激。谢谢。

Answer 1

traverse 与 fmap 相同，不同之处在于它还允许您在重建数据结构时运行效果。

查看 Data.Traversable 文档中的示例。

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

Tree 的 Functor 实例将是:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

它重建整个树，将 f 应用于每个值。

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

Traversable 实例几乎相同，只是构造函数是以应用程序风格调用的。这意味着我们在重建树时可能会产生(副作用)效果。 Applicative 与 monad 几乎相同，只是效果不能依赖于先前的结果。在此示例中，这意味着您无法根据重建左分支的结果对节点的右分支执行不同的操作。

由于历史原因，Traversable 类还包含 traverse 的单子(monad)版本，称为 mapM。出于所有意图和目的，mapM 与 traverse 相同 - 它作为单独的方法存在，因为 Applicative 后来才成为 的父类(super class)莫纳德。

如果您用不纯的语言实现此功能，fmap 将与 traverse 相同，因为无法防止副作用。您不能将其实现为循环，因为您必须递归地遍历数据结构。这是一个小例子，我将如何在 Javascript 中做到这一点:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

像这样实现它会限制您达到该语言允许的效果。如果你觉得想要非确定性(应用模型的列表实例)并且您的语言没有内置它，那么您就不走运了。