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

Question

applicative do notation / adovs. applicative lift via <$>/ mapon the first argument的评估顺序似乎有所不同，而<*>/apply对于其余参数。

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

1. 为什么解 1 和解 2 的求值顺序不同（一般概念）？
2. 如何重写解决方案 2（没有 ado），尊重测试中的预购断言？

给定的

可以在此处找到 PureScript by Example 书（第 7 章）中的练习：

3.（中）编写一个函数traversePreOrder :: forall a m b. Applicative m => (a -> m b) -> Tree a -> m (Tree b)来执行树的前序遍历。[...] Applicative do notation (ado) 是编写此函数的最简单方法。

代数数据类型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

解决方案2：常规提升（不起作用）

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

这会触发错误：

预期 [1,2,3,4,5,6,7]，得到 [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，而且在这里工作似乎也一样。）}