functional-programming - 如何将 ado 符号重写为通用应用提升，尊重评估顺序？

Question

applicative do notation的求值顺序好像有区别/ado与通过 <$> 进行的应用提升/map在第一个参数上，<*>/apply剩余参数。

至少，这是what I have read到目前为止，在下面所示的练习过程中反射(reflect)了什么。问题:

1. 为什么解决方案 1 和 2 的评估顺序不同(一般概念)？
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]

Answer 1

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，而且似乎在这里工作也一样。)}