有人可以解释Haskell中的遍历函数吗？

问题描述

我试图从 Data.Traversable 中找不到遍历函数。我无法看清楚它的意思。因为我来自一个必要的背景，有人可以根据一个命令循环向我解释吗？伪代码将非常感谢。谢谢。

解决方案

与 fmap ，除了它还允许您在重建数据结构时运行效果。

查看示例 Data.Traversable 文档。

 数据树a =空的|叶a |节点（Tree a）a（Tree a）
  

Functor 的实例可以是：

$ $ $ $ $ $ $ $ $ $>实例函子树其中
fmap f Empty =空
fmap f（Leaf x）= Leaf（fx）
fmap f（节点lkr）=节点（fmap fl）（fk）（fmap fr）

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

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $' = Leaf< $> f x
遍历f（节点l k r）=节点< $>遍历f l * f k *遍历fr

Traversable 实例几乎是同样，除了构造函数是以应用样式调用的。这意味着我们可以在重建树的时候产生（副作用）效果。除了效果不能取决于以前的结果之外，应用程序与monad几乎相同。在这个例子中，它意味着你不能做一些不同的事情，例如取决于重建左分支的结果。

由于历史原因， Traversable 类还包含单元版本的遍历，称为 mapM 。对于所有意图和目的， mapM 与遍历相同 - 它作为单独的方法存在，因为 Applicative 只是最近因为超类 Monad 。

如果你想实现这个在不纯的语言中， fmap 将与遍历相同，因为无法防止副作用。您不能将其实现为循环，因为您必须递归地遍历数据结构。这里有一个小例子，我将如何使用Javascript：

  Node.prototype.traverse = function（f）{
返回新节点（this.l.traverse（f），f（this.k），this.r.traverse（f））; 
 
 $ / code> 

像这样实现它限制了语言允许的效果。如果你f.e.想要非确定性（Applicative模型的列表实例）和你的语言没有内置，你是不幸的。

I am trying and failing to grok the traverse function from Data.Traversable. I am unable to see its point. Since I come from an imperative background, can someone please explain it to me in terms of an imperative loop? Pseudo-code would be much appreciated. Thanks.

解决方案

traverse is the same as fmap, except that it also allows you to run effects while you're rebuilding the data structure.

Take a look at the example from the Data.Traversable documentation.

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

The Functor instance of Tree would be:

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)

It rebuilds the entire tree, applying f to every value.

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

The Traversable instance is almost the same, except the constructors are called in applicative style. This means that we can have (side-)effects while rebuilding the tree. Applicative is almost the same as monads, except that effects cannot depend on previous results. In this example it means that you could not do something different to the right branch of a node depending on the results of rebuilding the left branch for example.

For historical reasons, the Traversable class also contains a monadic version of traverse called mapM. For all intents and purposes mapM is the same as traverse - it exists as a separate method because Applicative only recently because a superclass of Monad.

If you would implement this in an impure language, fmap would be the same as traverse, as there is no way to prevent side-effects. You can't implement it as a loop, as you have to traverse your data structure recursively. Here's a small example how I would do it in Javascript:

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

Implementing it like this limits you to the effects that the language allows though. If you f.e. want non-determinism (which the list instance of Applicative models) and your language doesn't have it built-in, you're out of luck.

这篇关于有人可以解释Haskell中的遍历函数吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！