爲什麼Haskell需要Data.Sequence當我們已經有了列表？

Question

List是Haskell的默認數據類型，爲什麼我們仍然需要Data.Sequence？ Data.Seq是否意味着可以隨機訪問的類似於C風格的數組？

如果是的話，我想這意味着Data.Sequence存儲在固定的內存緩衝區，因此，渴望評估類型。只是猜測，你會幫助糾正？謝謝。

Answer 1

列表類型是一個單鏈表。因此，前置，head和tail都是O（1）。但是，++是左邊列表大小的O（n）。

相比之下，Data.Sequence是一棵平衡樹，所以大部分操作都是O（log n）。這並不像O（1）那麼快，但它可能快得多O（n）。換句話說，你可以比列表更快地加入序列，但是前綴稍微慢一些。

除此之外，兩個數據結構都有相當類似的屬性;他們都懶惰，他們都是透明的。 （序列必須是有限雖然。）

參見從the documentation for Data.Sequence開場白：

通用有限序列。除了有限的操作和嚴格的操作之外，序列還與列表有所不同，有效地支持更廣泛的操作。

底層算法顯然是described here。 （特別是，包括一個漂亮的圖。）

如果你想陣列，你需要看看Data.Array和/或Data.Vector。