Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 datastructure 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.

like image 585
gatoatigrado Avatar asked Jun 13 '11 19:06

gatoatigrado


2 Answers

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

like image 95
Don Stewart Avatar answered Sep 21 '22 03:09

Don Stewart


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

like image 33
John L Avatar answered Sep 17 '22 03:09

John L