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中的列表中？

回答

相關問題