SML/NJ - 有效的方法或數據結構從頭開始訪問開始

Question

我正在製作一個程序，而我以爲使用的算法需要一種廉價的方式來訪問列表以使其有效。有沒有一種有效的方法來訪問最後一個元素的列表？或者，因爲我認爲這可能是不可能的，因爲SML列表的結構，是否有一個有效的數據結構來實現它？

數據的長度在執行之前是未知的，除了串行遍歷數據外，不需要其他數據。

Answer 1

我認爲你想要一個功能性的雙層屋頂。見例如Okasaki's paper on the subject。具體來說，圖5顯示了deques的實現。

Answer 2

如果使用功能性deque看起來像是矯枉過正，並且您只需要以相反順序遍歷列表一次，那麼解決方案（例如，使用List.last和List.take來模擬hd和tl，但是按照您看起來知道的那樣，倒序是相反的，因爲它們會使列表遍歷爲二次方。另一方面，內置函數rev非常高效，因爲它既是尾遞歸又是線性的。如果您向需要以相反順序遍歷該列表的函數提供列表，則一個簡單的解決方案是使用let使用rev進行綁定，以相反順序創建列表的本地副本，然後以常規方式遍歷反向列表。