我如何在Haskell中编写恒定空间长度函数？ [英] How do I write a constant-space length function in Haskell?

问题描述

长度的标准实现:: [a] - > Int 是：

  length [] = 0 
 length（x：xs）= 1 +长度xs 
  

这非常漂亮，但因使用线性空间而遭受堆栈溢出。

尾递归版本：
其中长度'[] n = n
长度'（x：xs）n =长度xs（n + 1）

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

当运行时，运行时并不累积许多（n + 1） thunk？不应该这个函数Haskell消耗O（n）空间并导致堆栈溢出？

（如果有问题，我使用GHC）$ / $>

解决方案

是的，您遇到了累积参数的常见陷阱。通常的治疗方法是对累积参数进行严格评估;为此，我喜欢严格的应用程序操作符 $！。如果你不强制严格，GHC的优化器可能会认为这个函数是严格的，但它可能不是。当然，这不是一件依赖于—有时候你希望一个积累的参数被懒惰地评估，O（N）空间就好，谢谢。

如何在Haskell中编写常量空间长度函数？

如上所述，使用严格的应用操作符来强制评估累积参数：

  clength xs = length'xs 0 
 where长度'[] n = n 
长度'（x：xs）n =长度'xs $！ （n + 1）
  

$！是（a - > b） - > a - > b ，它在应用函数之前强制评估 a 。

The canonical implementation of length :: [a] -> Int is:

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

which is very beautiful but suffers from stack overflow as it uses linear space.

The tail-recursive version:

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

doesn't suffer from this problem, but I don't understand how this can run in constant space in a lazy language.

Isn't the runtime accumulating numerous (n + 1) thunks as it moves through the list? Shouldn't this function Haskell to consume O(n) space and lead to stack overflow?

(if it matters, I'm using GHC)

解决方案

Yes, you've run into a common pitfall with accumulating parameters. The usual cure is to force strict evaluation on the accumulating parameter; for this purpose I like the strict application operator $!. If you don't force strictness, GHC's optimizer might decide it's OK for this function to be strict, but it might not. Definitely it's not a thing to rely on—sometimes you want an accumulating parameter to be evaluated lazily and O(N) space is just fine, thank you.

How do I write a constant-space length function in Haskell?

As noted above, use the strict application operator to force evaluation of the accumulating parameter:

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

The type of $! is (a -> b) -> a -> b, and it forces the evaluation of the a before applying the function.

这篇关于我如何在Haskell中编写恒定空间长度函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！