以下两个 lambda 函数的空间复杂度

我正在阅读以下内容：https://en.wikibooks.org/wiki/Haskell/Graph_reduction https://en.wikibooks.org/wiki/Haskell/Graph_reduction，其内容如下：

棘手的空间泄漏示例：

(\xs -> head xs + last xs) [1..n]
(\xs -> last xs + head xs) [1..n]

第一个版本运行于O(1)空间。第二个在O(n).

这个说法正确吗？我看不出它们有何不同。一旦执行，它们似乎都花费相同的时间和空间，并且在执行之前您可以惰性地确定它们的类型是兼容的。

实现此目的的一种方法是手动计算表达式，并观察中间表达式的最大长度如何作为以下函数增长：n。这比听起来更棘手，因为要共享xs在你的ambas的定义中，但我会这样做，希望它会有所帮助。

首先，我们来写一下定义head and last:

head :: [a] -> a
head (a:_) = a

last :: [a] -> a
last (a:[]) = a
last (_:as) = last as

现在，有了这个，让我们做第一个：

(\xs -> head xs + last xs) [1..n]
  => let xs = [1..n] in head xs + last xs
  => let xs = 1:[2..n] in head xs + last xs
  => let xs = 1:[2..n] in 1 + last xs
  => 1 + last [2..n]
  => 1 + last (2:[3..n])
  => 1 + last [3..n]
  => 1 + last (3:[4..n])
  .
  .
  .
  => 1 + last (n:[])
  => 1 + n

正如您所看到的，中间步骤中的表达式的大小有一些恒定的上限，并且n没关系。现在让我们尝试第二个示例。我选择通过在中创建绑定列表来说明结构共享和强制let grow:

(\xs -> last xs + head xs) [1..n]
  => let xs = [1..n] in last xs + head xs
  => let xs = 1:[2..n] in last xs + head xs
  => let xs  = 1:xs2
         xs2 = 2:[3..]
     in last xs2 + head xs
  => let xs  = 1:xs2
         xs2 = 2:xs3
         xs3 = 3:[4..]
     in last xs3 + head xs
  .
  .
  .
  => let xs  = 1:xs2
         xs2 = 2:xs3
         xs3 = 3:xs4
             .
             .
             .
         xsn = n:[]
     in last xsn + head xs
  => let xs  = 1:xs2
         xs2 = 2:xs3
         xs3 = 3:xs4
             .
             .
             .
         xsn = n:[]
     in n + head xs
  => n + 1

正如您所看到的，最大表达式的大小将与n。这意味着评估使用 O(n) 空间。

这两个示例之间的差异是由于以下事实造成的：+函数在强制第二个参数之前强制其第一个参数。作为一般规则，当您有一个具有多个参数的函数时，必须在其他参数之前强制其中一个参数，并且它发生的顺序可能会产生像这样的微妙影响。