haskell - 为什么在 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

让我们展开 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，它随后被 y3 定义中的 trace 使用，依此类推。