开发者

Fixed-size list in Haskell (i.e. array with list-like API)

Is there an efficient fixed-size list library in Haskell? I think the IArray interface is somewhat complicated when one only wants arrays indexed by natural numbers [including zero]. I want to write code like

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

my naive solution is below.

Edit: Sorry for the lack of context; I want a datastructur开发者_JAVA技巧e that can be allocated once, to avoid excessive garbage collection. This was in the context of the merge routine for merge sort, which takes two sorted sublists and produces a single sorted list.


How about using the vector package? It provides very efficient growable vectors with a list-like interface, and O(1) indexing.


I would probably use Vector as Don Stewart suggests, but you can use a list-like interface with IArray by using ListLike.


You might consider using a finger tree. It offers amortized O(1) cons, snoc, uncons, and unsnoc, and O(log n) split.


Here's my naive solution,

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)
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜