爲什麼OCaml只有first :: rest on list，而不是rest :: last for list？

Question

在OCaml中，對於列表，我們總是做first::rest。從列表中獲取第一個元素或在列表前插入一個元素很方便。

但爲什麼OCaml沒有rest::last？如果沒有List的函數，我們不能輕易地獲取列表的最後一個元素或將元素插入到列表的末尾。

Answer 1

列表數據類型不是一個神奇的內建函數，只是一個帶有一些語法糖的常規遞歸數據類型。你可以自己實現它，使用Nil代替[]和Cons(first,rest)代替first::rest，以下列方式：

type 'a mylist = 
    | Nil 
    | Cons of 'a * 'a mylist 

我不知道你是否會看到上面作爲一個回答你的問題的定義，但它確實如此：當你編寫first::rest時，你並沒有調用一個函數，而只是使用一個數據類型構造函數來構建一個新值（在恆定的時間和空間中）。

此定義簡單並具有明確的算法性能：列表是不可變的，訪問列表的第一個元素是O(1)，訪問k個元素是O(k)，兩個列表li1和li2的級聯是O(length(li1))等。特別是，訪問最後一個元素或在列表末尾添加一些東西li將是O(length(li));我們並不急於將此作爲一種便捷的操作，因爲它很昂貴。

如果要在序列末尾添加元素，列表不是正確的數據結構。您可能想要使用隊列（如果您遵循先入先出訪問規則），deque等。標準庫中有一個（可變的）Queue結構，並且兩個第三方覆蓋Core和Batteries有一個deque模塊（在Batteries中持久化，在Core中可變）。

Answer 2

由於名單是簡單地定義爲

type 'a list = Nil | Cons of 'a * 'a list 

除了你拼普通數據類型Nil爲[]和Cons爲綴::。換句話說，如果你願意，名單是「單一鏈接」的。除了構造函數的語法之外，沒有其他的魔法。顯然，爲了到達最後一個元素，或者追加一個元素，您需要一些輔助功能。