SML：如何将元素追加到SML中的列表中？

SML中是否有一个运算符，它允许我追加到列表而无需创建新列表？例如SML：如何将元素追加到SML中的列表中？

我不能做到这一点：

[1,2,3]::1

，但我可以这样做：

[1,2,3]@[1]

这是奇怪的，因为我必须创建一个有1名单。有没有更好的方法来做到这一点？

来源

2017-02-09 Har

正如@ sepp2k说，追加到列表的末尾是昂贵的。建立列表最慢的方法之一是将元素逐个附加到列表的最后，因为任何这样的方法在列表长度中最多只有二次方。出于这个原因，SML程序员有时会写一些函数，它们以倒序的方式创建列表（追加到前面而不是后面，即使在追加后面看起来更自然的情况下），然后通过“rev”运行结果列表是以一种聪明的方式实现的，因此它是'O（n）'）来获得所需的列表。 –

是否没有尾指针要追加到？这也将是O（1） – Har

@Har附加到尾指针（如果有甚至有一个，没有）会改变原始列表。 SML列表不可变，所以这是不可能的。 – sepp2k

你必须创建一个列表用一个在它无论哪种方式。 [1,2,3,1]尾部的尾巴的尾巴是[1]。所以如果你在内存中有[1,2,3,1]，你在内存中的某处也有[1]。

所以即使有像[1,2,3] @:: 1运营商，它不会有所作为，因为它仍然需要创建一个列表有一个在里面。

PS：xs @ [x]的真正问题不是创建列表，而是它的运行时在O（n）中（与O（1）中的相反）。这也是不可变单链表本质固有的问题，因此无法帮助，但这就是为什么你通常应该避免追加到这样的列表末尾。

来源

2017-02-09 23:46:47 sepp2k

1.您还将如何追加到列表中？ 2.他们不存储要添加到的尾指针吗？ 3. x :: xs究竟做了什么？创建一个新的列表或附加到头指针？ – Har

是否将SML中的列表实现为链接结构或数组？ – Har

@哈尔SML列表是*不可变*，单链表。它们完全等价于'datatype list'a =缺点'a *'列表|无'代替''''替代''''和'Nil'代替''''。所以他们非空的清单有一个头值，另一个清单是尾巴。这些都不能改变。 'x :: xs'创建一个新的列表，其中'x'作为头部值，'xs'作为尾部。 – sepp2k

[1,2,3]::1试图将int列表[1,2,3]附加到整数值1，这是不可能的，因为无法附加整数。然而，
1::[1,2,3]是作为列表[1,2,3]完全有效的支持追加操作。为::评价规则需要t1 :: t1 list，其中T1为1型的值，而T1列表是1型的列表，你在做什么是t1 list :: t1。
[1,2,3] @ [1]是有效的，因为您将列表追加到列表中。

来源

2017-08-06 12:53:53 Selhar

SML：如何将元素追加到SML中的列表中？

回答

相关问题