lisp - 在 Lisp 和其他函数式语言中，为什么长度不是 O(1)

Question

Lisp 中的列表原语具有如下定义的运算符长度:

(define (length lst)
  (if (null? lst) 0 (+ 1 (length (cdr lst)))))

为什么某些 Lisp 的实现者不能使 length 成为在恒定时间内计算的原语？

谢谢

Answer 1

原因是 Lisp 中列表的“传统”实现。在其他地方，有时列表的实现类似于数组。因此，当您创建一个列表时，它是一个独立的东西。

An array-like list: [ 1 2 3 4 5 6 ]

如果您想将一个项目(例如“0”)附加到该列表的开头(并假设列表实现很简单)，列表中的所有项目都将向上移动(向右移动) ).然后，“0”将安装在新位置。

Step 0. [ 1 2 3 4 5 6 ]
Step 1. [   1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)

(传统的)Lisp 列表根本不是这样的。列表中的每一项都是指向下一项的单独部分。列表的各个部分称为“conses”。 (这称为链表。)

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

嗯？好吧，这些项目中的每一个都是一个缺点。每个 cons 单元格都有两个值:car 和 cdr。 (当 cons 单元格与列表一起使用时，最好将“car”和“cdr”视为“first”和“rest”。“First”包含您希望列表包含的任何数据，例如数字，甚至链接到其他列表。“Rest”包含列表的其余部分。实际上你也可以将任何你想要的内容放入“rest”部分，但我们将在这里忽略它。)“Nil”是“空列表”，基本上表示“列表已结束!”

那么，如果我们想再次在前面添加一个“0”怎么办？

[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

看到了吗？我们刚刚创建了一个指向旧列表开头的新 cons 单元格。您会听到人们将此称为“consing”到前面的值。但是，您会注意到列表的其余部分没有受到影响。

好的，但为什么有人想要这个？您可以共享列表。假设您想要两个基本相同的列表。只是现在您想要一个列表以“7”开头，而另一个列表以“4”开头？好吧，使用类似数组的方式，我们必须有两个列表。

[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]

如果您将“5”替换为“13”并分享更改会怎么样？

[ 7 0 1 2 3 4 13 6 ]
[ 4 0 1 2 3 4 5 6 ]

您有两个完全独立的列表。如果您想共享更改，则必须在两个列表中进行更改。

传统的 Lisp 列表会怎样？首先，在前面贴上一个“7”和一个“4”:

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
   /
[4]

是的。我们刚刚做了两个都指向旧列表的 cons。列表的其余部分是共享的。而且，如果我们用“13”替换“5”:

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [13] -> [6] -> nil
   /
[4]

两个列表都得到了更改，因为其余的是共享的。

所有这一切的要点在于，与许多人所期望的不同，传统的 Lisp 列表并不是一个单一的东西。它们是一堆相互指向的小东西(conses)，形成一条链，也就是链表。如果你想得到链条的长度，你必须跟踪所有的小链接，直到你到达终点，nil。因此，O(n) 长度。

如果 Lisp 列表像数组一样完成，那么它们的复杂度可以达到 O(1)。我敢肯定一些晦涩的 Lisp 会这样做，并完全摆脱链表(conses)。但是，cons 似乎是进入几乎所有流行的 Lisp 方言的东西之一。如果您想要 O(1) 长度和查找，它们中的大多数也提供数组或向量。

---

链表的乐趣:

 -----------------<------------------------<----------
|                                                     |
 --> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -->

这个链表最终指向它自己。如果你使用你的长度函数，它将永远循环，寻找结束，但永远找不到。