applicative do notation的求值顺序好像有区别/ado
与通过 <$>
进行的应用提升/map
在第一个参数上,<*>
/apply
剩余参数。
至少,这是what I have read到目前为止,在下面所示的练习过程中反射(reflect)了什么。问题:
- 为什么解决方案 1 和 2 的评估顺序不同(一般概念)?
- 我如何重写解决方案 2(没有
ado
),尊重测试中的预序断言?
给出
可以找到 PureScript by Example 书中的练习(第 7 章)here :
3.(Medium) Write a function
traversePreOrder :: forall a m b. Applicative m => (a -> m b) -> Tree a -> m (Tree b)
that performs a pre-order traversal of the tree. [...] Applicative do notation (ado) is the easiest way to write this function.
代数数据类型 Tree
:
data Tree a
= Leaf
| Branch (Tree a) a (Tree a)
测试预期遍历顺序 [1,2,3,4,5,6,7]
:
Assert.equal (1 .. 7)
$ snd
$ runWriter
$ traversePreOrder (\x -> tell [ x ])
$ Branch (Branch (leaf 3) 2 (leaf 4)) 1 (Branch (leaf 6) 5 (leaf 7))
注意:我不确定,什么tell
和 runWriter
完全正确 - 这是从练习中复制的代码块。
为了说明 - 示例树如下所示:
我尝试了什么
解决方案 1:ado
(作品)
traversePreOrder :: forall a m b. Applicative m => (a -> m b) -> Tree a -> m (Tree b)
traversePreOrder f Leaf = pure Leaf
traversePreOrder f (Branch tl v tr) = ado
ev <- f v
etl <- traversePreOrder f tl
etr <- traversePreOrder f tr
in Branch etl ev etr
方案二:常规提升(不起作用)
traversePreOrder :: forall a m b. Applicative m => (a -> m b) -> Tree a -> m (Tree b)
traversePreOrder f Leaf = pure Leaf
traversePreOrder f (Branch tl v tr) =
let
ev = f v -- I consciously tried to place this evaluation first, does not work
etl = traversePreOrder f tl
etr = traversePreOrder f tr
in
Branch <$> etl <*> ev <*> etr
这会触发错误:
expected [1,2,3,4,5,6,7], got [3,2,4,1,6,5,7]
最佳答案
let ev = f v -- I consciously tried to place this evaluation first, does not work etl = traversePreOrder f tl etr = traversePreOrder f tr in Branch <$> etl <*> ev <*> etr
源代码顺序在函数式编程中无关紧要。你可以把这些 let
任何顺序的声明,它都会工作相同 - 它们会创建相同的值,并且这些值将描述相同的计算,并且在相同的表达式中使用时将形成相同的程序。
这里真正重要的“评估顺序”是您正在使用的应用仿函数的一个属性 - 应用效果 的应用顺序。该订单由 Applicative
的运营商管理您在这里使用的类型类,即 <*>
:据记载,首先从左侧应用效果,然后从右侧应用效果。因此,要实现预序遍历,您必须编写
traversePreOrder :: forall a m b. Applicative m => (a -> m b) -> Tree a -> m (Tree b)
traversePreOrder f Leaf = pure Leaf
traversePreOrder f (Branch tl v tr) =
(\ev etl etr -> Branch etl ev etr) <$> f v <*> traversePreOrder f tl <*> traversePreOrder f tr
(免责声明:我不是很了解 PureScript,但它看起来很像 Haskell,而且似乎在这里工作也一样。)
关于functional-programming - 如何将 ado 符号重写为通用应用提升,尊重评估顺序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65155989/