Haskell 编写 myLength

Question

我在这个页面上工作

http://www.haskell.org/haskellwiki/99_questions/Solutions/4

我理解每个函数的含义，看到一个函数可以像这样以多种方式定义，这很有趣。但是，我刚开始想知道哪个更快。我认为它会是 length 中的 Prelude 。

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

但是，这比 length 中的 Prelude 慢得多。

在我的计算机上， length 中的 Prelude 在 0.37 秒内返回 [1..10^7] 的长度。然而，上面定义的函数需要 15.26 秒。

我定义了自己的长度函数，它使用了累加器。只用了 8.99 秒。

我想知道为什么会出现这些巨大的差异？

Answer 1

当您说“length 中的 Prelude 返回 ... 在 0.37 秒内”时，您指的是哪个编译器？如果您正在使用 GHC，您可以看到，例如 here 实际实现与简单的不同

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

即，它是:

length l = len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

此代码使用累加器，并通过使用未装箱的整数避免了巨大的未评估 thunk 的问题，即此版本是高度优化的。

为了说明“简单”版本的问题，请考虑如何评估 length [1, 2, 3]:

length [1, 2, 3]
  => 1 + length [2, 3]
  => 1 + (1 + length [3])
  => 1 + (1 + (1 + length []))
  => 1 + (1 + (1 + 0))

直到真正需要它的结果时才会评估总和，因此您看到当输入是一个巨大的列表时，您将首先在内存中创建一个巨大的总和，然后仅在真正需要其结果时才对其进行评估。

相比之下，优化版本的评估如下:

length [1, 2, 3]
  => len [1, 2, 3] 0#
  => len [2, 3] (1#)
  => len [3] (2#)
  => len [] (3#)
  => 3

即“+1”立即完成。