Haskell中的固定大小列表（即具有類列表API的數組）

Haskell中是否存在有效的固定大小列表庫？我認爲IArray接口有點複雜，當一個人只想要由自然數[包括零]索引的數組。我想寫代碼如Haskell中的固定大小列表（即具有類列表API的數組）

zeroToTwenty :: Int -> FixedList Int 
zeroToTwenty 0 = createFixedList 21 [] 
zeroToTwenty n = zeroToTwenty (n-1) `append` n

我的天真解決方案如下。

編輯：對不起，缺乏上下文的;我想要一個可以分配一次的數據結構，以避免過多的垃圾回收。這是在合併排序的merge例程的上下文中，它採用兩個排序的子列表並生成單個排序列表。

來源

2011-06-13 gatoatigrado

你對這個數據類型的期望是什麼，列表不給你？是O（1）索引嗎？你願意去換取O（1）索引嗎？ – augustss 2011-06-14 13:10:36

@augustss查看編輯 – gatoatigrado 2011-06-14 20:09:26

那麼，我仍然不知道你期望什麼操作。一次分配的東西也必須在Haskell中一次性填充內容。除非你想使用可變數據結構。 – augustss 2011-06-14 20:20:48

我可能會使用Vector作爲Don Stewart的建議，但您可以使用ListLike與IArray使用類似列表的界面。

來源

2011-06-13 21:37:56

我希望提問者知道'ListLike'包裝數組不會奇蹟般地提供一個O（1）時間缺點。（請參閱唐斯圖爾特答案的提問者的評論。） – 2011-06-14 00:41:45

@Tayyoshi Ito：這是一個很好的觀點。 'ListLike'只是一個界面;實現的性能特徵不會改變。如果'cons'和索引都很重要，我可能會建議Data.Sequence。但需要更多的背景來提出真正的建議。 – 2011-06-14 14:00:26

這是我天真的解決方案，

import Data.Array.Diff 
newtype FixedList a = FixedList (Int, (DiffArray Int a)) 
createFixedList n init = FixedList (0, array (0, n - 1) init) 
append (FixedList (curr, array)) v = FixedList (curr + 1, array // [(curr, v)]) 

instance Show a => Show (FixedList a) where 
    show (FixedList (curr, arr)) = show $ take curr (elems arr)

來源

2011-06-13 19:46:50 gatoatigrado

順便說一下，diff數組已被棄用，並且它們的性能也相當差。 – 2011-06-13 20:00:48

@唐斯圖爾特：謝謝！ Vector是最好的替代品嗎？ – gatoatigrado 2011-06-13 20:10:39

如何使用vector包？它提供了具有類似列表界面的非常高效的可生成矢量，以及索引。

來源

2011-06-13 20:00:28

對不起，懶惰;它說包裝頁面上的「cons」是O（n） - 這不是我想要的（雖然我確信我會使用vector，現在我知道它了）。 – gatoatigrado 2011-06-13 20:07:06

確實，cons是* O（n）*。但是，您可以通過'replicate'和其他組合器有效地創建一個固定大小的矢量。只是遠離列表 - ish'cons'。 – 2011-06-13 20:09:04

嗯，我想要一個list-ish API :)，也許我只是將它與下面的內容結合起來？ – gatoatigrado 2011-06-13 20:12:40

您可以考慮使用一個finger tree。它提供了分期償還的O（1）cons，snoc，uncons和unnoc，以及O（log n）分割。

來源

2011-06-14 18:47:58

Haskell中的固定大小列表（即具有類列表API的數組）

回答

相關問題