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

Question

applicative do notation/ado 的评估顺序与第一个参数上通过 <$>/map 的应用提升似乎有所不同，<*>/apply 剩余参数。

至少，这是 what I have read 到目前为止，以及在下面所示的练习过程中所反映的内容。问题：

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