Kon*_*nan 94 haskell traversal
我正在尝试并且未能完成该traverse功能Data.Traversable.我无法理解其观点.由于我来自一个势在必行的背景,有人可以根据命令性循环向我解释一下吗？伪代码将非常感激.谢谢.
Sjo*_*her 113
traversefmap除了它还允许您在重建数据结构时运行效果时,它是相同的.
看一下Data.Traversable文档中的示例.
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
该Functor实例Tree是:
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实例几乎是相同的,除了构造函数的调用在应用性的风格.这意味着我们可以在重建树时获得(侧面)效果.应用与monad几乎相同,只是效果不能取决于之前的结果.在此示例中,这意味着您无法对节点的右侧分支执行不同的操作,具体取决于重建左侧分支的结果.
由于历史原因,Traversable该类还包含一个traverse被调用的monadic版本mapM.因为所有意图和目的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));
}
像这样实现它会限制您使用语言允许的效果.如果你想要非确定性(应用模型的列表实例)和你的语言没有内置,那你就不走运了.
Lan*_*dei 55
traverse将事物内部Traversable转化Traversable为"内部"的事物Applicative,给定一个能够使Applicative事物变得简单的功能.
让我们使用Maybeas Applicative并列为Traversable.首先我们需要转换功能:
half x = if even x then Just (x `div` 2) else Nothing
因此,如果数字是偶数,我们得到一半(在a内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]什么？
我们得到了部分结果[1],[2,2]并[3,3,3]使用了rep.现在列出的语义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]]
ham*_*mar 41
我认为这是最容易理解的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将结构中的每个元素转换为一些应用程序,然后从左到右排序这些应用程序的效果,返回包含结果的相同形状的结构.
您还可以将其与Foldable定义相关函数的比较traverse_.
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用于其他类型的容器或使用其他应用程序时,事情变得更有趣.
Kai*_*ren 16
它有点像fmap,除了你可以在mapper函数中运行效果,它也会改变结果类型.
想象一下表示数据库中用户ID的整数列表:[1, 2, 3].如果要将fmap这些用户ID用于用户名,则不能使用传统的fmap,因为在函数内部需要访问数据库来读取用户名(这需要一个效果 - 在这种情况下,使用IOmonad).
签名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仅适用于monad,而traverse更通用.
如果你只是想实现一个效果并且不返回任何有用的值,那么这些函数的版本traverse_和mapM_版本都会忽略函数的返回值并且稍微快一些.
traverse 是循环.它的实现取决于要遍历的数据结构.这可能是一个列表,树Maybe,Seq(uence),或任何具有的通过像一个for循环或递归函数被走过的通用方式.数组将具有for循环,列表具有while循环,树可以是递归的,或者是堆栈与while循环的组合; 但在函数式语言中,您不需要这些繁琐的循环命令:将循环的内部部分(以函数的形状)与数据结构以更直接的方式组合,并且更简洁.
使用Traversable类型类,您可以编写更加独立且通用的算法.但我的经验表明,这Traversable通常仅用于将算法简化为现有数据结构.很高兴不需要为不同的数据类型编写类似的函数.