如何在Haskell中编写一个恒定空间长度函数？

Question

规范的实现length :: [a] -> Int是:

length [] = 0
length (x:xs) = 1 + length xs

这是非常漂亮的,但由于它使用线性空间而遭受堆栈溢出.

尾递归版本:

length xs = length' xs 0
  where length' [] n = n
        length' (x:xs) n = length xs (n + 1)

不会遇到这个问题,但我不明白这是如何在懒惰的语言中以恒定的空间运行的.

运行时(n + 1)列表中的运行时是否累积了大量的thunks？这个函数Haskell不应该消耗O(n)空间并导致堆栈溢出吗？

(如果重要的话,我正在使用GHC)

Answer 1

是的,你遇到了累积参数的常见陷阱.通常的办法是对累积参数进行严格评估; 为此,我喜欢严格的应用程序运算符$!.如果你不强制严格,GHC的优化器可能会认为这个函数是严格的,但它可能不是.肯定不是依赖它 - 有时候你想要一个累积的参数被懒惰地评估,O(N)空间就好了,谢谢.

如何在Haskell中编写一个恒定空间长度函数？

如上所述,使用严格的应用程序运算符强制评估累积参数:

clength xs = length' xs 0
  where length' []     n = n
        length' (x:xs) n = length' xs $! (n + 1)

$!is 的类型(a -> b) -> a -> b,它强制a在应用函数之前进行评估.

Answer 2

在GHCi中运行第二个版本:

> length [1..1000000]
*** Exception: stack overflow

所以回答你的问题:是的,它确实会遇到这个问题,就像你期望的那样.

但是,GHC比普通编译器更聪明; 如果您使用优化结果进行编译,它将为您修复代码并使其在恒定空间中工作.

更一般地说,有一些方法可以在Haskell代码中的特定点强制严格,防止构建深层嵌套的thunk.的通常的例子是foldl与foldl':

len1 = foldl (\x _ -> x + 1) 0
len2 = foldl' (\x _ -> x + 1) 0

这两个函数都是左边的折叠,它们执行"相同"的操作,除了foldl在foldl'严格的情况下是懒惰的.结果是len1在GHCi中具有堆栈溢出的模具,同时len2正常工作.