我正在尝试从Data.Traversable
中摸索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
实例几乎相同,只是构造函数以应用样式调用。这意味着我们在重建树时可能会产生(副作用(。应用几乎与单子相同,只是效果不能取决于以前的结果。在此示例中,这意味着您无法根据重建左分支的结果对节点的右侧分支执行不同操作。
由于历史原因,Traversable
类还包含一个名为 mapM
的 traverse
的一元版本。出于所有意图和目的mapM
与traverse
相同 - 它作为一个单独的方法存在,因为Applicative
后来才成为Monad
的超类。
如果你用不纯的语言实现这一点,fmap
将与traverse
相同,因为没有办法防止副作用。您不能将其实现为循环,因为您必须递归遍历数据结构。这里有一个小例子,我将如何在Javascript中做到这一点:
Node.prototype.traverse = function (f) {
return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}
但是,像这样实现它限制了语言允许的效果。如果你想要非确定性(应用模型的列表实例(,而你的语言没有内置它,那么你就不走运了。
traverse
将Traversable
内的事物变成Applicative
"内部"事物的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]
。两个[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 -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f
sequenceA
从左到右将结构的元素排序在一起,返回具有相同形状的结构,其中包含结果。
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
之间的主要区别在于后者允许您保留结构的形状,而前者需要您将结果折叠成其他值。
其用法的一个简单示例是使用列表作为可遍历结构,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
用于其他类型的容器或使用其他应用程序时,事情会变得更加有趣。
这有点像fmap
,除了你可以在映射器函数内运行效果,这也会改变结果类型。
假设一个表示数据库中用户 ID 的整数列表:[1, 2, 3]
。如果要将这些用户 ID fmap
为用户名,则不能使用传统的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
还有一个名为mapM
的函数:
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
任何mapM
的使用都可以用traverse
代替,但不能反过来。 mapM
只适用于monads,而traverse
更通用。
如果你只是想实现一个效果而不返回任何有用的值,这些函数有traverse_
和mapM_
版本,它们都忽略了函数的返回值,速度略快。
traverse
是循环。它的实现取决于要遍历的数据结构。这可能是一个列表、树、Maybe
、Seq
(uence(,或者任何通过 for 循环或递归函数等具有通用遍历方式的东西。数组将有一个 for 循环,一个列表一个 while-loop,一个树要么是递归的东西,要么是堆栈与 while-loop 的组合;但是在函数式语言中,你不需要这些繁琐的循环命令:你以更直接的方式和更少的冗长方式将循环的内部部分(以函数的形式(与数据结构相结合。
使用 Traversable
类型类,您可以编写更独立和通用的算法。但我的经验表明,Traversable
通常仅用于简单地将算法粘附到现有数据结构中。也不需要为不同的数据类型编写类似的函数,这很好。