Haskell：從後面訪問列表

今天我開始學習Haskell。我對函數式語言很有興趣，我很享受Haskell。Haskell：從後面訪問列表

但是我有一個關於它的設計的問題，它讓我感到困惑：從我迄今爲止所瞭解的內容來看，訪問元素到列表的後面看起來要複雜得多，像xs:x，其中xs::[a]和x::a似乎不可能）。（從我的理解）可以追加一個列表到另一個（xs++[a]），但它會花費更多的運行時（它需要遍歷整個列表），它不能用於模式匹配。

爲什麼Haskell缺少這樣的操作？

來源

2011-01-22 peoro

列表數據類型

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

被定義如上。只有兩種模式可以匹配：[]和x : xs，其中x是頭部，xs是尾部。

前面加上一個列表

a = 1 : 2 : [] 
b = 0 : a

 
(:) <-- b 
/\ 
0 (:) <-- a 
/\ 
    1 (:) 
    /\ 
    2 []

只是增加了一個新的利弊細胞並重新使用原來的列表作爲尾巴。

但是請記住，Haskell數據結構是不可變的。追加到一個列表

a = 1 : 2 : [] 
b = a ++ [3]

 
(:) <-- a  (:) <-- b 
/\   /\ 
1 (:)   1 (:) 
/\   /\ 
    2 []   2 (:) 
        /\ 
        3 []

的尾部需要構建一個全新的列表，因爲沒有原始結構的一部分，可重複使用。

事實上，考慮

a = 0 : a 
b = 0 : [ x+1 | x <- b ]

 
(:) <-- a   (:) <-- b 
/\    /\ 
0 (:) <-- a  0 (:) <-- [ x+1 | x <- b ] 
/\    /\ 
    0 (:) <-- a  1 (:) <-- [ x+1 | x <- [ x+1 | x <- b ] ] 
    ...    ...

如何將你得到列表的最後一個元素，或追加到最後？

還有其他的數據結構，例如dequeue，它們更適合用於前臺和後臺訪問。

來源

2011-01-22 17:42:07 ephemient

這些不是語言問題，只是List數據類型，它具有一些特殊的語法，但不完全是「Haskell的組成部分」。你在C中使用單向鏈表的問題相同，但這顯然不是C編程語言的問題。

如果你想要一個帶有尾指針的雙向鏈表，然後製作這樣的數據類型並使用它！您可能想要了解更多數據類型（例如，參見containers包，vector和dlist包）。

來源

2011-01-22 17:30:19

列表是一個_built-in_類型，由Haskell語言本身描述，不是嗎？如果Haskell中的列表被定義爲它是由於語言設計的原因，就像C語言所定義的內置類型一樣。 C中的列表不是該語言的一部分，就像非本地Haskell數據類型不是Haskell語言的一部分一樣。 – peoro 2011-01-22 18:07:25

@peoro列表構建的程度純粹是句法。想象一下，如果list被定義爲`data List a = Nul |缺點（列表a）`。它的內置程度與您的問題是正交的 - 如果您想要O（1）訪問尾部，則使用追蹤尾部的數據結構。 – 2011-01-22 18:12:17

今天我學會了如何聲明新的類型，並理解你告訴我`:-)` – peoro 2011-01-25 17:36:02

這是純List數據結構的問題，而不是haskell本身。您可以閱讀Purely Functional Data Structures紙以瞭解有關其他純數據結構的更多信息，這些數據結構可以在此類操作上具有更好的性能

來源

2011-01-22 17:33:40 Yuras

它取決於。列表是一種_built-in_類型，由Haskell語言本身描述，不是嗎？如果是這樣，哈斯克爾列表取決於語言設計。 – peoro 2011-01-22 18:07:58

Haskell中的列表數據類型是鏈接列表，因此查找使用O（n）時間。如果您需要頻繁訪問列表後面，您可能需要查看Data.Sequence ，其中O（1）添加到開頭和結尾。爲了回答Haskell爲什麼使用這個數據結構作爲「標準容器」（如C和數組），這是因爲Haskell是一種純粹的函數式語言，因此偏好純粹的函數式數據結構（不可變和持久化）。進一步閱讀請看this wiki page。要在Haskell中使用非功能性數據結構，將需要它位於IO或ST monad中。

來源

2011-01-22 17:38:17 HaskellElephant

不要害怕反轉（）你的名單，只要你需要。在給定遞歸函數之前將列表逆轉，或者顛倒fold（）的最終結果並不罕見。

來源

2011-01-25 17:25:40 Harmen

Haskell：從後面訪問列表

回答

相關問題