为什么列表的串联需要O（n）？

这是因为状态不变。列表是对象+指针，因此，如果我们将列表想象为元组，则它可能如下所示：

let tupleList = ("a", ("b", ("c", [])))

现在，让我们使用“ head”功能获得此“列表”中的第一项。这个head函数花费O（1）时间，因为我们可以使用fst：

> fst tupleList

如果我们想将列表中的第一项换成其他项，我们可以这样做：

let tupleList2 = ("x",snd tupleList)

这也可以在O（1）中完成。为什么？因为列表中绝对没有其他元素存储对第一个条目的引用。由于状态不变，我们现在有两个列表，tupleList和tupleList2。当我们完成时，tupleList2我们没有复制整个列表。因为原始指针是不可变的，所以我们可以继续引用它们，但可以在列表的开头使用其他内容。

现在，让我们尝试获取3个项目列表的最后一个元素：

> snd . snd $ fst tupleList

这发生在O（3）中，它等于我们列表的长度，即O（n）。

但是我们不能存储指向列表中最后一个元素的指针并在O（1）中访问它吗？为此，我们需要一个数组，而不是一个列表。数组允许任何元素的O（1）查找时间，因为它是在寄存器级别实现的原始数据结构。

（ASIDE：如果不确定为什么我们要使用链表而不是数组，那么您应该更多地了解数据结构，数据结构算法以及诸如get，poll，insert等各种操作的Big-O时间复杂度，删除，排序等）。

现在我们已经确定了这一点，让我们看一下串联。让我们tupleList结合一个新列表("e", ("f", []))。为此，我们必须遍历整个列表，就像获取最后一个元素一样：

tupleList3 = (fst tupleList, (snd $ fst tupleList, (snd . snd $ fst tupleList, ("e", ("f", [])))

上述操作实际上是更糟糕的不是O（n）的时间，因为在列表中的每个元素，我们必须重新读取列表中最多的是指数。但是，如果我们暂时忽略它，而将重点放在关键方面：为了到达列表中的最后一个元素，我们必须遍历整个结构。

您可能会问，为什么我们不只是将最后一个列表项存储在内存中？这样，可以在O（1）中完成附加到列表末尾的操作。但不是很快，我们不能在不更改整个列表的情况下更改最后一个列表项。为什么？

让我们来看看它的外观：

data Queue a = Queue { last :: Queue a, head :: a, next :: Queue a} | Empty
appendEnd :: a -> Queue a -> Queue a
appendEnd a2 (Queue l, h, n) = ????

如果我修改“ last”（这是一个不可变的变量），则实际上我不会修改队列中最后一项的指针。我将创建最后一个项目的副本。引用该原始项目的所有其他内容将继续引用该原始项目。

因此，为了更新队列中的最后一个项目，我必须更新所有引用它的内容。这只能在最佳O（n）时间内完成。

因此，在我们的传统清单中，我们有最后一项：

List a []

但是，如果我们要更改它，我们会对其进行复制。现在，倒数第二个项目引用了旧版本。因此，我们需要更新该项目。

List a (List a [])

但是，如果我们更新倒数第二个项目，则会对其进行复制。现在，倒数第三项有一个旧参考。因此，我们需要对其进行更新。重复直到我们到达列表的开头。我们来了一圈。没有任何内容引用列表的开头，因此编辑需要O（1）。

这就是Haskell没有双向链接列表的原因。这也是为什么无法以传统方式实现“队列”（或至少是FIFO队列）的原因。在Haskell中进行排队需要对传统数据结构进行一些认真的重新思考。

如果您对所有这些工作原理都感到更加好奇，请考虑购买《纯粹功能数据结构》一书。

编辑：如果您曾经看过：http : //visualgo.net/list.html，您可能会注意到在可视化中，“插入尾巴”发生在O（1）中。但是为了做到这一点，我们需要修改列表中的最后一个条目以为其赋予新的指针。更新指针会改变纯函数式语言所不允许的状态。希望在我的其余帖子中可以明确这一点。