Haskell 惰性和 seq

Question

我试图理解 Haskell 中的惰性和 seq:

• 在 (1) 中，在基本情况中的打印需要 v 之前不会对 v 进行求值，这是否正确？

• 在 (2) 中，在每次递归调用之前计算 v' 是否正确，以便在基本情况下不需要计算 v ？如果不是，我该如何实现这种严格的评估？

• 有什么分析工具可以让我自己确认这两点吗？

main = do
  f [1, 2, 3, 4] 0
  f' [1, 2, 3, 4] 0

g x = 42 * x -- this could be whatever

-- 1. lazy
f [] v = print v -- base case
f (x:xs) v = f xs v'
  where v' = v + g x

-- 2. strict
f' [] v = print v -- base case
f' (x:xs) v = seq v' f' xs v'
  where v' = v + g x

我知道 foldl 和 foldl' 在这些情况下会做我想要的事情。我更感兴趣的是了解这是如何实现的。

Answer 1

是的，你说得对。

在操作上，在情况 1 中，变量 v 绑定(bind)到一个 thunk，这是一个未计算的表达式，它会变得越来越大，直到 print 强制其计算。内存占用不是恒定的。

在情况 2 中，变量 v 始终绑定(bind)到计算的数字。递归在恒定空间中运行。

顺便说一句，seq v' f' xs v' 的惯用法是写成

v' `seq` f' xs v'

(这是等效的，因为应用程序始终对功能严格)或利用 $!

f' xs $! v'

另一个常见的选择是使用 bang 模式并忘记 seq

f' [] !v = print v -- base case
f' (x:xs) !v = f' xs v'
  where v' = v + g x

刘海!确保立即请求v，因此即使它是一个thunk，也会在继续之前对其进行评估。这也确保了恒定的内存占用。

作为严格性的分析工具，您可以尝试 Debug.Trace.trace，只要需要某些 thunk，它就会打印调试消息。这不适用于一般输出，但用于一般调试就可以了。