3

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]

4

1 回答 1

6 
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 并且似乎在这里工作相同。）

于 2020-12-05T14:26:53.000 回答