Haskell中的固定大小列表（即具有类似列表的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

Haskell中是否有一个有效的固定大小列表库?我认为当一个人只想要用自然数[包括零]索引的数组时,IArray接口有点复杂。我想写代码

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.

编辑:抱歉缺乏上下文;我想要一个可以分配一次的数据结构,以避免过多的垃圾收集。这是在合并排序的合并例程的上下文中,它采用两个排序的子列表并生成一个排序列表。

4 个解决方案

#1

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

我可能会使用Vector作为Don Stewart的建议,但你可以使用ListLike与IArray使用类似列表的界面。

#2

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

如何使用矢量包?它提供了非常有效的可扩展向量,具有类似列表的接口和O(1)索引。

#3

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

您可以考虑使用手指树。它提供摊销的O(1)缺点,snoc,uncons和unsnoc,以及O(log n)拆分。

#4

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)

#1