A list of fixed sizes in Haskell (i.e. an array with an API list)

Question

Does Haskell have an effective fixed-size list library? I think the IArray interface is a bit more complicated when you need only 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 the data structure to be allocated once to avoid excessive garbage collection. This was in the context of the merge sort routine, which takes two sorted sublists and creates one sorted list.

Answer 1

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

Answer 2

How about using a vector package? It provides very efficient growing vectors with a list and O (1) interface.

Answer 3

You might want to use the folder tree. It offers amortized O (1) cons, snoc, uncons and unsnoc, and O (log n).

Answer 4

Here is my naive decision

 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)