Haskell中的列表：數據類型還是抽象數據類型？

據我所知，Haskell中的列表類型是使用鏈表在內部實現的。但是，該語言的用戶沒有看到實現的細節，也沒有能力修改組成鏈接列表的「鏈接」以允許它指向不同的內存地址。我想這是在內部完成的。Haskell中的列表：數據類型還是抽象數據類型？

那麼，那麼列表類型是否可以像Haskell一樣被限定呢？它是「數據類型」還是「抽象數據類型」？什麼是實現的鏈表類型？

此外，由於Prelude提供的列表類型不是鏈表類型，因此如何實現基本鏈表功能？

舉個例子來說，這個代碼段設計成一個列表的索引n在添加的元素的：

add [] acc _ _ = reverse acc 
add (x:xs) acc 0 a = add xs (x:a:acc) (-1) a 
add (x:xs) acc n a = add xs (x:acc) (n-1) a

使用「真正的」鏈接列表，添加元素也只是由修改的一個指向內存地址的指針。這在Haskell中是不可能的（或者是？），因此問題是：我的實現是向最好的列表添加一個元素，還是缺少一些東西（我認爲使用reverse函數尤其如此醜，但它可能沒有？）

請不要猶豫，糾正我，如果我說的是錯誤的，並感謝您的時間。

來源

2009-12-21 CharlieP

歡迎來到StackOverflow！偉大的第一個問題 – Sampson 2009-12-21 19:53:00

http://en.wikibooks.org/wiki/Haskell/List_processing – 2009-12-21 19:57:13

感謝所有回答我的問題的人，儘管我只能將其中的一個標記爲我的「接受的答案」，但您都非常有幫助。 – CharlieP 2009-12-22 10:52:17

您對數據結構的可變性感到困惑。它是一個正確的列表 - 只是不允許你修改。 Haskell純粹是功能性的，意味着值是不變的 - 你不能改變列表中的項目，而不能將數字2變爲3.相反，你需要執行計算以創建新值，並根據需要進行更改。

您可以定義功能最簡單的是這樣的：

add ls idx el = take idx ls ++ el : drop idx ls

名單el : drop idx ls重用原始列表的尾部，所以你只需要產生一個新的列表達idx（這是什麼take功能確實）。如果你想使用顯式遞歸做到這一點，你可以像這樣定義它：

add ls 0 el = el : ls 
add (x:xs) idx el 
    | idx < 0 = error "Negative index for add" 
    | otherwise = x : add xs (idx - 1) el 
add [] _ el = [el]

這重用列表以同樣的方式尾（這是在第一種情況下el : ls）。

由於看起來這是一個鏈表，所以讓我們清楚一下鏈表是什麼：它是一個由單元格組成的數據結構，其中每個單元格都有一個值和對下一個項目的引用。

struct ListCell { 
void *value; /* This is the head */ 
struct ListCell *next; /* This is the tail */ 
}

在Lisp中，它被定義爲(head . tail)，其中head是價值和tail是參照下一個項目：在C，因爲它可能被定義。

在Haskell，它的定義爲data [] a = [] | a : [a]，其中a是值和[a]是參照下一個項目。

正如你所看到的，這些數據結構都是等價的。唯一的區別是在C和Lisp中，它們不是純粹的功能，頭部和尾部值是可以改變的東西。在Haskell中，你不能改變它們。

來源

2009-12-21 20:39:33 Chuck

Haskell是一個純粹的函數式編程語言。這意味着根本不能做任何改變。

列表是非抽象類型，它只是一個鏈表。

你可以認爲這種方式定義他們的：

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

這正是被定義的鏈接列表的方式 - 一個頭元素（指針）休息。

請注意，這在內部沒有區別 - 如果您想要更高效的類型，請使用Sequence或Array。（但由於不允許更改，所以您不需要實際複製列表以便區分副本，所以這可能是性能增益而不是命令式語言）

來源

2009-12-21 19:56:07 Dario

事實上，內部模塊GHC.Types定義爲「infixr 5：」。數據[] a = [] | a：[a]' – ephemient 2009-12-21 19:57:54

我還是不明白爲什麼上面定義的列表類型是一個鏈表。由於Haskell是純粹的功能，我知道數據是不可變的，但我試圖反對程序員在Haskell編碼時使用的實際列表，以及編譯爲較低級別語言時GHC實現這些列表。對不起，如果我的問題不夠清楚。 – CharlieP 2009-12-21 20:22:06

CharlieP，你正在尋找的指針，但沒有找到任何。考慮Java，它也缺少指針。在純Java中建立一個鏈表是不可能的？不，當然不。你將會引用一個頭對象，它本身會有一個值和一個對列表中下一個對象的引用。添加一個標記對象來指示列表的結尾，然後就完成了。這正是給定的類型定義所說的。你不需要顯式的指針來創建鏈表。你只需要鏈接。誰在乎GHC在底下做什麼？ – 2009-12-21 21:44:26

您的代碼可能有效，但絕對不是最佳選擇。您想在索引0中插入一個項目一個例子就拿情況：如果按照這個推導

add [200, 300, 400] [] 0 100

，你結束了：

add [200, 300, 400] [] 0 100 
add [300, 400] (200:100:[]) (-1) 100 
add [400] (300:[200, 100]) (-2) 300 
add [] (400:[300, 200, 100]) (-3) 400 
reverse [400, 300, 200, 100] 
[100, 200, 300, 400]

但我們只需要添加一個項目到列表的開頭！這樣的操作很簡單！它是（:)

add [200, 300, 400] [] 0 100 
100:[200, 300, 400] 
[100, 200, 300, 400]

想想多少名單真的需要扭轉。

您詢問運行時是否修改鏈接列表中的指針。因爲Haskell中的列表是不可變的，所以沒有人（甚至是運行時）修改鏈表中的指針。這就是爲什麼，例如，將一個項目追加到列表的前面是很便宜的，但是在列表的後面添加一個元素卻很昂貴。當您將一個項目追加到列表的前面時，您可以重新使用所有現有的列表。但是當你在最後追加一個項目時，它必須建立一個全新的鏈接列表。爲了使列表前面的操作便宜，數據的不變性是必需的。

來源

2009-12-21 20:41:11

另請注意，如果您給它一個無限列表，那麼算法會執行什麼操作。 KABOOM！ – Chuck 2009-12-21 21:30:12

非常好的一點！ – 2009-12-21 21:38:27

回覆：添加元素到列表的末尾，我建議使用(++)運營商和splitAt功能：

add xs a n = beg ++ (a : end) 
    where 
    (beg, end) = splitAt n xs

的List是一個鏈表，但它是隻讀的。您無法修改List，而是創建一個新的List結構，該結構包含您想要的元素。我沒有閱讀，但this book可能會得到您的基本問題。

HTH

來源

2009-12-21 20:47:17

在Haskell，「數據類型」和「抽象類型」是本領域的術語：

A「數據類型」（這是不抽象）具有可見值構造您可以在case表達式或函數定義上進行模式匹配。
「抽象類型」沒有可見值構造函數，因此您無法在該類型的值上進行模式匹配。

給定一個類型a，[a]（的a列表）是一個數據類型，因爲你可以在可見的構造利弊模式匹配（書面:）和零（書面[]）。一個抽象類型的例子是IO a，你不能通過模式匹配來解構。

來源

2009-12-22 02:57:52

編譯器可以自由選擇任何想要列表的內部表示。實際上它確實有所不同。顯然，列表「[1 ..]」不是作爲經典的cons系列單元來實現的。

事實上，一個懶惰列表存儲爲一個thunk，其計算結果爲包含下一個值和下一個thunk的cons單元（一個thunk基本上是一個函數指針加上函數的參數，它被實際值替換一旦函數被調用）。另一方面，如果編譯器中的嚴格性分析器可以證明整個列表總是被評估的，那麼編譯器只會將整個列表創建爲一系列的cons單元。

來源

2009-12-22 07:13:06

Haskell中的列表：數據類型還是抽象數據類型？

回答

相關問題