有人可以解释Haskell中的遍历函数吗？
我是Haskell的新手。 我正在尝试和无法从Data.Traversable模块Data.Traversable的traversefunction。 我无法看清楚这一点。 既然我来自一个必要的背景，有人可以请一个必要的循环来解释吗？ 一个伪代码将不胜感激。 谢谢。
traverse与fmap相同，只是它还允许您在重build数据结构时运行效果。
看一下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 (fx) fmap f (Node lkr) = Node (fmap fl) (fk) (fmap fr)
它重build整个树，对每个值应用f 。
instance Traversable Tree where traverse f Empty = pure Empty traverse f (Leaf x) = Leaf <$> fx traverse f (Node lkr) = Node <$> traverse fl <*> fk <*> traverse fr
Traversable实例几乎是一样的，除了构造函数是以应用样式调用的。 这意味着我们可以在重build树的时候产生（side-）效果。 除了效果不能取决于以前的结果之外，应用程序与monad几乎相同。 在这个例子中，这意味着你不能做一些不同的东西到一个节点的右分支取决于重build左分支的结果。
Traversable类还包含一个mapM版本的mapM ，其中的效果可能原则上取决于以前的结果。 （虽然你绝对不应该这样做）。例如，如果左分支为Empty ，则执行两次f的效果：
mapM f (Node lkr) = do l' <- mapM fl k' <- case l' of Empty -> do _ <- fk; fk _ -> fk r' <- mapM fr return $ Node l' k' r'
如果你用一种不纯的语言来实现它， fmap和traverse与mapM是一样的，因为没有办法防止副作用。 您不能将其实现为循环，因为您必须recursion地遍历数据结构。 这里有一个小例子，我将如何使用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 “内部”的东西，给一个函数，使得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
原因是用<*>函数来build立结果，当其中一个参数是Nothing ，我们得到Nothing 。
另一个例子：
rep x = replicate xx
这个函数生成一个长度为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] 。 两次[1,2]和[3,3,3]所有组合是六次[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]]
我认为就sequenceA而言最容易理解，因为traverse可以定义如下。
traverse :: (Traversable t, Applicative f) => (a -> fb) -> ta -> f (tb) traverse f = sequenceA . fmap f
sequenceA将结构的元素从左到右排列在一起，返回包含结果的相同形状的结构。
sequenceA :: (Traversable t, Applicative f) => t (fa) -> f (ta) sequenceA = traverse id
您也可以将sequenceA视为颠倒两个函数的顺序，例如从一个动作列表转到一个返回结果列表的动作。
因此， traverse采用了一些结构，并将结构中的每个元素都转化为一个应用，然后将这些应用的副作用从左到右进行sorting，返回一个包含结果的相同形状的结构。
你也可以把它和Foldable比较，它定义了相关的函数traverse_ 。
traverse_ :: (Foldable t, Applicative f) => (a -> fb) -> ta -> f ()
所以你可以看到Foldable和Traversable之间的关键区别在于后者允许你保留结构的形状，而前者要求你将结果折叠成其他的值。
一个简单的使用例子是使用一个列表作为遍历结构， 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"]
当然，在这种情况下，它相当于Prelude中的mapM 。 使用其他types的容器或使用其他应用程序时，它会变得更有趣。
这有点像fmap ，除了你可以在mapper函数中运行副作用，这也会改变结果types。
想象一下在数据库中代表用户ID的整数列表： [1, 2, 3] 。 如果您想将这些用户ID fmap到用户名，则不能使用传统的fmap ，因为在函数内部需要访问数据库来读取用户名（这需要一个副作用 – 在这种情况下，使用IO monad ）。
traverse的签名是：
traverse :: (Traversable t, Applicative f) => (a -> fb) -> ta -> f (tb)
随着traverse ，你可以做副作用，因此，你的代码映射用户名到用户名如下所示：
mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String] mapUserIDsToUsernames fn ids = traverse fn ids
还有一个叫做mapM的函数：
mapM :: Monad m => (a -> mb) -> [a] -> m [b]
任何对mapM使用都可以用traverse来代替，而不是相反。 mapM通常比traverseperformance得更好，但是mapM只适用于带有列表的monad，而traverse更通用。
如果你只是想达到副作用而不返回任何有用的值，这些函数的traverse_和mapM_版本都会忽略来自函数的返回值，并且稍微快一些。
traverse 是循环。 其实现取决于要遍历的数据结构。 这可能是一个List，Tree，Maybe，Seq（ence），或者任何通过某种方法遍历的通用方法。 像一个for循环或recursion函数。 一个数组将有一个for循环，一个List循环，一棵树或者。 recursion或堆栈与while循环的组合; 但是在函数式语言中，您不需要这些繁琐的循环命令：将循环的内部（以函数的forms）与数据结构以更直接的方式组合起来，而不是冗长的。
使用Traversable typeclass，你可能会写出更独立和多function的algorithm。 但是我的经验表明，Traversable通常只是用来简单地将algorithm粘贴到现有的数据结构上。 不需要为不同的数据types编写类似的函数也是很好的。
