Python有列表构造函数吗?

9
Python是否有像OCaml(::)或lisp中的cons那样的列表构造函数,它接受一个head元素和tail列表,并返回一个新的列表head::tail? 我搜索了Python列表构造函数,但找到的是与__init__有关的其他内容。例如,请参见Creating a list in Python- something sneaky going on? 澄清一下,我要找的是Python中以下列表分解的反函数(在此问题中找到)
head, *tail = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
这将会得到:

>>>head
1
>>> tail
[1, 2, 3, 5, 8, 13, 21, 34, 55]
我正在寻找一个列表构造器,例如cons::,以便...
head :: tail  =>   original list

谷歌“Python教程”……话说:foo = [1,2,3,4] 或者 foo = list(1,2,3,4,5) - DTSCode
2
@DTSCode list(1, 2, 3 , 4, 5) 不起作用 :-) - mgilson
4
你能否描述一下你想做什么,对于那些不太熟悉OCaml或Lisp的人来说? - mgilson
1
Python中的列表并不是其他语言所使用的那种意义上的列表。它们实际上是数组。 - Tom Karzes
2
从已删除的答案中复制此评论:“在Lisp风格的语言中,列表是一种递归数据结构,由其第一个项目(头部)和包含其余项目(尾部)的列表组成。因此,构造列表的自然操作是取现有列表并在开头添加一个项目;新列表具有新项目作为其头部,旧列表作为其尾部。” - hobbs
@mgilson,我已根据建议添加了澄清。 - thor
4个回答

阿里云服务器只需要99元/年,新老用户同享,点击查看详情
15

回答您的问题,通常在所谓的“函数式”语言(如Lisp、OCaml、Haskell等)中找到的 cons 没有直接等效物。

这是因为在编程语言中有两种竞争模型来表示元素列表。

链表

你似乎熟悉的那一种被称为链表。

链表由cons单元组成,每个单元包含两个引用:

  • 第一个引用指向列表中的一个元素,称为头部
  • 另一个引用指向列表中的下一个cons单元,即尾部

因为列表很少是无限的,所以最后一个const单元通常会指向一个特殊值——空列表,有时称为nil

如果您想将列表保存在变量中以备将来参考,您需要保留对第一个cons单元的引用。

这是来自维基百科的可视化表示

在这个模型中,每个列表必须通过在前面添加元素来构造,创建一个新的cons单元,将新元素指向其头部,并将先前构建的子列表指向其尾部。这就是为什么 cons 运算符有时被称为列表构造器的原因。

数组

这通常是Python等命令式语言首选的模型。在该模型中,列表只是对内存范围的引用。

假设您像这样创建一个列表:

l = [1, 2, 3]

每当你创建一个列表时,Python 会为它分配一小段内存来存储元素,并留有一些额外的空间以备将来添加元素。要存储它,你只需存储对第一个元素的引用,以及对内存范围大小的引用,就像这样:

l  <-- your variable
|     ___ ___ ___ ___ ___ ___ ___ ___ ___
|->  |   |   |   |   |   |   |   |   |   |
     | 1 | 2 | 3 |   |   |   |   |   |   |
     |___|___|___|___|___|___|___|___|___|

如果您决定在列表末尾添加一个元素,您可以使用append方法。

l.append(4)

形成以下列表:

 ___ ___ ___ ___ ___ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
| 1 | 2 | 3 | 4 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|

假设你忘记了一个初始的0,现在希望在开头添加它。你可以使用插入方法(插入位置为0):

l.insert(0, 0)

但是列表开头没有空间!Python别无选择,只能一个一个地将每个元素复制到直接右侧的位置:

 ___ ___ ___ ___ ___ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
| 1 | 2 | 3 | 4 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|
  |   |   |__ |___
  |   |___   |    |  First, Python has to copy the four elements
  |___    |  |    |  one space to the right 
 ___ _\/ _\/ \/_ _\/ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
|   | 1 | 2 | 3 | 4 |   |   |   |   |
|___|___|___|___|___|___|___|___|___|

Only then can it insert the 0 at the beginning

 ___ ___ ___ ___ ___ ___ ___ ___ ___
|   |   |   |   |   |   |   |   |   |
| 0 | 1 | 2 | 3 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|___|

对于这样一个小的数组来说,可能看起来并不算什么,但是想象一下,如果你的数组很大,并且你重复执行此操作多次:你将花费很多时间构建列表!

这就是为什么使用数组作为列表的语言(如Python)中没有列表构造函数。

更深入的探究:为什么有两种不同的模型?

你现在可能会想知道为什么不同的语言会选择不同的列表模型,以及这两种模型中哪一种更优秀。

这是因为这两种数据结构在不同的上下文中具有不同的性能。以下是两个例子:

访问中间元素

假设你想要获取列表的第五个元素。

在链表中,你需要获取:

  • 第一个 cons 单元格
  • 然后获取该单元格的尾部以获取第二个元素
  • 然后获取该单元格的尾部以获取第三个元素
  • 然后获取该单元格的尾部以获取第四个元素
  • 最后再获取该单元格的尾部以获取第五个元素

因此,你必须通过 5 个引用进行访问!

用数组来做就简单多了:你知道第一个元素的引用。只需要访问右边 4 个位置的引用,因为这些元素都在连续的内存范围内!

如果你需要多次访问非连续的元素列表,那么数组会更好。

在中间插入元素

现在想象一下,你想要在列表中间插入一个元素。

使用链表:

  • 找到插入点之前的最后一个元素对应的 cons 单元格。
  • 创建一个新的 cons 单元格,其头部指向你要添加的元素,尾部与你刚刚定位的 cons 单元格相同。
  • 现在可以更改该单元格的尾部,使其指向新创建的单元格。

使用数组,就像在中间添加元素时一样,您需要将插入点右侧的每个元素向右移动一个空间!

在这种情况下,链表显然更加优秀。


7
有人建议你执行以下操作:
a = 1
b = [2, 3, 4, 5]
c = [a] + b
只要blist类型,这将起作用。然而,通常情况下,您将使用一个既是列表又是元组的对象,或者是其他可迭代对象(在此插入您喜欢的可迭代对象)。在这种情况下,您最好这样做:
a = 1
b = (2, 3, 4, 5)
c = [a]
c.extend(b)
这使整个过程与b的类型无关(这使您的代码更具“鸭子特性”,这可能很好)。当然,还有其他选项...例如,您可以选择使用itertools
import itertools
a = 1
b = [2, 3, 4, 5]
lazy_c = itertools.chain([a], b)

我们有一个好处,那就是不用关心可迭代对象b的类型,并且我们还得到了惰性迭代的好处——我们不会创建新的列表或元组。我们只会创建一个对象,在你迭代它时会产生相同的结果。这可以节省内存(有时也可以节省CPU的循环),但如果b也是一种类似生成器的对象,并且同时在其他地方被迭代,那么可能会产生意想不到的后果(这种情况不经意间很少发生)。


在你的第二段中,第一句话:“假设ab都是list类型。”... 只有b需要是list类型。当a出现在方括号内时,它将被转换为列表形式[a] - Kevin J. Chase
1
@KevinJ.Chase -- 是的。谢谢你指出来。我想我的观点是,使用+连接序列(通常)只有在两个序列类型相同时才有效。 - mgilson

6

Python中的列表是可变的,而OCaml的列表具有不可变值语义。但是如果a是一个项目,b是一个列表,您可以使用[a] + b来获得所需的结果,它将返回一个新列表,其中包含a后面的b中的项,不会修改ab中的任何一个。不过,构建列表的更常见模式是通过appendextend原地进行。


1
你可以使用列表拼接。
head = 1
tail = [2,3,4]
lst = [head] + tail # [1,2,3,4]

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,