Haskell列表的內部表示？

哈斯克爾支持一些基本的操作，通過列表遞歸，像head，tail，init和last。我在內部想知道Haskell如何表示其列表數據？如果它是單鏈表，那麼init和last操作可能會隨着列表的增長而變得昂貴。如果它是一個雙向鏈表，所有四種操作可以在一些內存爲代價進行O(1)很容易，雖然。無論哪種方式，知道這一點很重要，所以我可以編寫適當的代碼。（儘管函數式編程的精神似乎是「問它做什麼，而不是它如何做」）。Haskell列表的內部表示？

來源

2013-02-25 limp_chimp

「問做什麼的，它不是如何做它」不，如果你關心寫代碼，是相當快;） – 2013-02-25 10:11:35

那麼，這就是我認爲:-)因此，我的問題。 – 2013-02-25 10:36:09

「如果這是一個雙向鏈表，可以由所有四種操作O（1）很容易」其實，如果你想留下純粹的功能它不是那麼容易，所以普通的雙向鏈表沒有在Haskell使用多。在保持純功能的同時做所有的事情需要更復雜的數據結構 - 但事實證明，通過利用哈斯克爾的懶惰，你可以進一步研究_O_（1）操作（或者以某種方式分期_O_（ _n_），這幾乎是一樣好）在它的單鏈式鏈表上比在任何程序語言中都是可能的。 – leftaroundabout 2013-02-25 19:59:44

列表，只表示爲......單鏈表。定義爲：

data [] a = [] | a : [a]

，你可以寫爲：

data List a = Empty | Cons a (List a)

內存佈局完全由這個定義。

構造函數是堆中分配
內部多態性字段是指向其他分配的節點
脊柱是懶惰

所以，你最終的東西是這樣的：

enter image description here

所以head是O（1）這種結構，而last或(++)是O（n）的

沒有魔法在Haskell數據結構 - 其直接的定義，使其完全清楚的複雜性將是什麼（模懶惰）。如果你需要不同的複雜性，使用不同的結構（如IntMap，序列，HashMap中，矢量等）...

來源

2013-02-25 08:51:56

感謝您的回答。我不確定有必要強調這個答案應該是多麼明確/明顯 - 我是Haskell的初學者，而來自C這是一個巨大的變化，所以我仍然在計算一些東西。無論如何，再次感謝。 – 2013-02-25 09:38:21

哦，我並不是說它很「容易」，只是沒有魔法而已。如果您只是查看數據類型定義，則全是可導出的。 – 2013-02-25 11:08:26

兩大注意事項：**懶惰**和**融合**。懶惰意味着，例如，在'xs ++ ys'中，您只需支付追加的費用即可遍歷結果列表;頭（xs ++ ys）'是O（1），而不是O（n）。融合意味着許多操作不會超過遍歷的成本。例如'map（* 2）（xs ++ ys）'的成本低於'map（* 2）'和'++'的成本總和，因爲GHC消除了生成的中間列表。 – 2013-02-25 21:58:37

Haskell的列表被單獨聯繫，所以cons，head和tail是O（1），同時init和last是O（Ñ）。

如果您需要更好的性能，請考慮使用來自Data.Sequence的Seq類型，該類型提供對列表兩端的O（1）訪問權限。它在內部使用2-3 finger trees。

來源

2013-02-25 08:50:22

Haskell列表的內部表示？

回答

相關問題