为什么在 Haskell 中右折叠时打印会影响顺序？

Question

我确定这与惰性求值有关，但我仍然无法解释为什么会这样。为什么在 verboseAdd2 中评估右侧会反转调试跟踪输出？

这是代码：

import Debug.Trace

data BinaryTree = Empty | Node Int BinaryTree BinaryTree

instance Show BinaryTree where
  show Empty = "_"
  show (Node x Empty right) = unwords [           show x, show right]
  show (Node x left  right) = unwords [show left, show x, show right]

add :: Int -> BinaryTree -> BinaryTree
add v Empty = Node v Empty Empty
add v a@(Node x left right)
  | v == x = a
  | v <  x = Node x (add v left) right
  | v >  x = Node x left (add v right)

verboseAdd :: Int -> BinaryTree -> BinaryTree
verboseAdd v a = trace ("[1] Adding v=" ++ show v) (add v a)

verboseAdd2 :: Int -> BinaryTree -> BinaryTree
verboseAdd2 v a = trace ("[2] Adding v=" ++ show v ++ " to " ++ show a) (add v a)

verbosePlus :: (Num a, Show a) => a -> a -> a
verbosePlus left right = trace (show left ++ " + " ++ show right)
                               (left + right)

main :: IO()
main = do
  let seq = [1,2,3,4,5]
  in do print $ foldr verbosePlus 0 seq
        putStrLn ""
        print $ foldr verboseAdd Empty seq
        putStrLn ""
        print $ foldr verboseAdd2 Empty seq

这是输出：

5 + 0
4 + 5
3 + 9
2 + 12
1 + 14
15

[1] Adding v=1
[1] Adding v=2
[1] Adding v=3
[1] Adding v=4
[1] Adding v=5
1 _ 2 _ 3 _ 4 _ 5 _

[2] Adding v=5 to _
[2] Adding v=4 to 5 _
[2] Adding v=3 to 4 _ 5 _
[2] Adding v=2 to 3 _ 4 _ 5 _
[2] Adding v=1 to 2 _ 3 _ 4 _ 5 _
1 _ 2 _ 3 _ 4 _ 5 _

Answer 1

这里有很多评论，但似乎没有人写过回答...

答案当然是show函数。当您说 x = add 5 myTree 时，您实际上所做的只是将 x 设置为未计算的表达式。 y = add 7 x 将 y 设置为另一个未计算的表达式，依此类推。但是当你尝试 show y 时......好吧，y 取决于 x，所以首先我们必须评估 x。就是为什么 trace 按顺序打印的原因。

Answer 2

让我们在

中扩展foldr

foldr verboseAdd2 Empty [1, 2, 3, 4, 5]

使用其定义（将 verboseAdd2 缩写为 va）：

1 `va` (2 `va` (3 `va` (4 `va` (5 `va` Empty))))

或者，在这种情况下，如果我们使用前缀表示法可能会更简单：

va 1 $ va 2 $ va 3 $ va 4 $ va 5 Empty

根据 va 的定义，这减少到

let y1 = va 2 $ va 3 $ va 4 $ va 5 Empty
in trace ("Adding v=1 to " ++ show y1) (add 1 y1)

通过展开更多出现的 va，我们得到

let y4 = trace ("Adding v=5 to " ++ show Empty) (add 5 Empty) in
let y3 = trace ("Adding v=4 to " ++ show y4) (add 4 y4) in
let y2 = trace ("Adding v=3 to " ++ show y3) (add 3 y3) in
let y1 = trace ("Adding v=2 to " ++ show y2) (add 2 y2) in
trace ("Adding v=1 to " ++ show y1) (add 1 y1)

希望你能从这里看到最外面的trace中的show y1，我们首先需要评估y1，这会导致trace ("Adding v=2 to " ++ show y2")开火，这迫使y3，依此类推，直到我们到达 y4。 y4 中的 trace 不需要强制执行任何其他操作，因此它最终可以打印其消息，然后继续计算 add 5 Empty，然后由 [=21= 使用]在y3的定义中，依此类推。

为什么在 Haskell 中右折叠时打印会影响顺序？

Why does printing affects order when right folding in Haskell?

haskell

lazy-evaluation

trace

evaluation