arrays - Haskell 中的大小索引可变数组

Question

在 Haskell 中，可以在大小索引列表上编写函数，以确保我们永远不会越界。一个可能的实现是:

data Nat = Zero | Succ Nat deriving (Eq, Ord, Show)

infixr 5 :-

data Vec (n :: Nat) a where
    Nil  :: Vec 'Zero a
    (:-) :: a -> Vec n a -> Vec ('Succ n) a       

data Fin (n :: Nat) where
    FZ :: Fin ('Succ n)
    FS :: Fin n -> Fin ('Succ n)                       

vLookup :: Vec n a -> Fin n -> a
vLookup Nil _ = undefined           
vLookup (x :- _) FZ = x
vLookup (_ :- xs) (FS i) = vLookup xs i                      

当然，这对于不可变大小的索引列表(又名Vec)来说就很好了。

但是可变的呢？是否可以在 Haskell 中定义(或者是否有库)可变大小索引数组？如果没有这样的库，如何实现呢？

编辑1:我搜索了Hackage并且没有找到任何与我的描述相匹配的库(大小索引可变数组)。

编辑2:我想提一下，我认为使用IORef来获得所需的可变性:

 type Array n a = IORef (Vec n a)

但我想知道是否有更好(更高效、更优雅)的选择...

Answer 1

这样的类型does exist on Hackage .

我会避免类似type Array n a = IORef (Vec n a)。可变数组最重要的是效率。如果你不需要它快速运行/内存占用低，那么使用它们就没有多大意义——即使是“可变算法”通常也更容易在 Haskell 中使用函数式风格来表达，也许使用状态 monad，但没有真正的破坏性可变状态。
但如果效率很重要，那么您还需要严格的高速缓存高效存储。 Unboxed vectors是理想的。 OTOH，Vec 在运行时数据级别上与普通列表没有什么不同，当然在缓存一致性方面没有那么好。即使您将它们定义为实际上将可变性交织到列表脊柱中，它也不会比在纯函数风格中使用不可变 Vec 更好。

所以，如果我必须写这么简单的东西，我宁愿将一个(不安全的、长度方向的)未装箱的可变arrox包装在一个长度索引的新类型中。

import qualified Data.Vector.Unboxed.Mutable as VUM

newtype MVec (s :: *) (n :: Nat) (a :: *)
        = MVec { getMVector :: VUM.MVector s a }

然后，您可以定义一个接口(interface)，使所有经过类型检查的公共(public)操作都是长度安全的，同时仍然保留 MVector 的性能配置文件。