有人能解释一下哈斯克尔的遍历函数吗？

小开

我认为最容易理解的是 sequenceA，因为 traverse可以定义为接下来。

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

sequenceA sequences together the elements of a structure from left to right, returning a structure with the same shape containing the results.

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

您也可以将 sequenceA看作是两个函数的顺序颠倒，例如从一个操作列表转换为返回一个结果列表的操作。

所以 traverse采用某种结构，应用 f将结构中的每个元素转换成某种应用程序，然后将这些应用程序的效果从左到右排序，返回一个包含结果的相同形状的结构。

您还可以将其与定义相关函数 traverse_的 Foldable进行比较。

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

因此，您可以看到 Foldable和 Traversable之间的关键区别在于，后者允许您保留结构的形状，而前者要求您将结果折叠成其他值。

其用法的一个简单示例是使用 list 作为可遍历结构，使用 IO作为应用程序:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

虽然这个示例相当平淡无奇，但当 traverse用于其他类型的容器或使用其他应用程序时，事情就变得更有趣了。

小开

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实例几乎相同，只不过构造函数是以应用程序样式调用的。这意味着我们可以在重建树时产生(副作用)。应用几乎与单子相同，除了效果不能依赖于以前的结果。在本例中，这意味着您不能根据重建左分支的结果(例如)对节点的右分支执行不同的操作。

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 later became a superclass of Monad.

如果你用一种不纯粹的语言来实现它，那么 fmap将和 traverse一样，因为没有办法防止副作用。您不能将其实现为循环，因为您必须递归地遍历数据结构。下面是我在 Javascript 中的一个小例子:

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

像这样实现它会限制您获得语言所允许的效果。如果你想要非决定论(即 Applicative 模型的列表实例) ，而你的语言没有内置它，你就不走运了。

小开

traverse将 Traversable内部的事物转换成 Traversable内部的事物，给定一个函数使 Applicative变成事物。

让我们使用 Maybe作为 Applicative，列出为 Traversable。首先我们需要转换函数:

half x = if even x then Just (x `div` 2) else Nothing

所以如果一个数是偶数，我们得到它的一半(在 Just中) ，否则我们得到 Nothing。如果一切都“顺利”，它看起来是这样的:

traverse half [2,4..10]
--Just [1,2,3,4,5]

但是..。

traverse half [1..10]
-- Nothing

原因是使用了 <*>函数来构建结果，当其中一个参数是 Nothing时，我们得到了 Nothing。

另一个例子:

rep x = replicate x x

这个函数生成一个长度为 x的列表，内容为 x，例如 rep 3 = [3,3,3]。traverse rep [1..3]的结果是什么？

我们用 rep得到了 [1]、 [2,2]和 [3,3,3]的部分结果。现在，像 Applicatives这样的列表的语义是“采用所有组合”，例如，(+) <$> [10,20] <*> [3,4]是 [13,14,23,24]。

[1]和 [2,2]的“所有组合”是 [1,2]的两倍。所有2倍于 [1,2]和 [3,3,3]的组合都是6倍于 [1,2,3]。所以我们有:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

小开

循环。它的实现取决于要遍历的数据结构。这可能是一个列表、树、 Maybe、 Seq(uence) ，或者任何通过 for 循环或递归函数来遍历的通用方法。一个数组应该有一个 for 循环，一个列表，一个 while 循环，一个树，或者一些递归的东西，或者堆栈和 while 循环的组合; 但是在函数式语言中，你不需要这些繁琐的循环命令: 你可以用一种更直接的方式将循环的内部部分(以函数的形式)与数据结构结合起来，减少冗长。

使用 Traversable类型类，您可以编写更加独立和通用的算法。但是我的经验告诉我，Traversable通常只用于将算法简单地粘贴到现有的数据结构上。不需要为限定的不同数据类型编写类似的函数，这是相当不错的。

小开

它有点像 fmap，只不过您可以在 mapper 函数中运行效果，这也会改变结果类型。

想象一个表示数据库中用户 ID 的整数列表: [1, 2, 3]。如果您想要 fmap这些用户 ID 到用户名，您不能使用传统的 fmap，因为在函数内部您需要访问数据库来读取用户名(这需要一种效果——在本例中，使用 IO monad)。

traverse的签名如下:

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

使用 traverse，您可以实现效果，因此，将用户 ID 映射到用户名的代码如下所示:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

There's also a function called mapM:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Any use of mapM can be replaced with traverse, but not the other way around. mapM only works for monads, whereas traverse is more generic.

如果您只想实现一个效果而不想返回任何有用的值，那么这些函数有 traverse_和 mapM_版本，它们都忽略了函数的返回值，并且稍微快一些。