“`foldTree`”和递归版本之间的计算顺序有什么不同？

Question

 -- Top-down
treeDown' :: Tree a -> [a]
treeDown' (Node x xs) = x : concat (map treeDown' xs)

-- Bottom-up
treeUp' :: Tree a -> [a]
treeUp' = foldTree f
  where
    f x ns = x : concat ns

对我来说，这两种版本在以下方面都是等价的：

value

• evaluation
• 输出顺序(自下而上)

有人告诉我在foldTree版本中，

foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f = go where
    go (Node x ts) = f x (map go ts)

f在完成递归下降之后就会饱和，然后从子节点和它们的subForests返回。这就是为什么它执行“自下而上”的评估命令，而另一个版本是“自上而下”的原因。

这很有道理。然而，我看到treeDown'版本也发生了同样的情况。在x计算完成之前，不能将map treeDown' xs添加到列表中。当然，由于懒散，实际的评价顺序可能会发生变化。

因此，我想知道，仅仅基于这些定义，treeDown'和treeUp'不是完全等价的吗？

Answer 1

我不明白当f饱和时，它为什么重要。这些函数是相同的算法，它们以相同的顺序处理树。因为懒惰，那份订单是自上而下的。

在Haskell中观察评估顺序是很棘手的，这也是因为懒惰。但是GHCI为我们提供了工具来查看发生了什么，看treeUp'和treeDown'的行为是否相同。

首先，我们定义了一种构建一个小示例树的方法，以便以后我们可以检查该树中有多少已经被检查过：

mkTree :: Int -> Tree Int
mkTree 0 = Node 0 []
mkTree n = Node n [mkTree (n - 1)]

接下来，我们需要一个工具来计算函数对新树的遍历，打印第一个项来强制它，然后返回整个遍历和输入树：

first :: (Tree Int -> [Int]) -> IO (Tree Int, [Int])
first f = let t = mkTree 3
              xs = f t 
          in print (head xs) *> pure (t, xs)

然后调用我们要测试的两个函数中的每一个，保存结果：

Prelude> down <- first treeDown'
3
Prelude> up <- first treeUp'
3

注意到，正如预期的那样，每个输出都只是3，这是示例树的根。在将树的根放在遍历的顶部之前，它们中的任何一个都会执行额外的递归工作吗？我们可以使用GHCI的:sprint命令找到答案，它显示了一个值有多少是强制的：

Prelude> :sprint up
up = (<Node> 3 [_],3 : _)
Prelude> :sprint down
down = (<Node> 3 [_],3 : _)

事实上，正如我所说的，这两个函数的行为是相同的。每个用户只查看输入树的根，以计算结果列表的第一个项，直到有人请求另一个项时，树的其余部分才会被发现。