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 但没有真正的破坏性可变状态。
但如果效率很重要，那么您还需要紧凑的 cache-efficient 存储空间。 Unboxed vectors 很理想。 OTOH，Vec是在运行时间数据级别上，和普通列表没有什么区别，当然在缓存一致性方面没那么好。即使您将它们定义为实际将可变性交织到列表脊柱中，它也不会比在 pure-functional 样式中使用不可变 Vecs 更好。

所以，如果我不得不写这么简单的东西，我宁愿将（不安全，length-wise）未装箱的可变 arrox 包装在 length-indexed 新类型中。

import qualified Data.Vector.Unboxed.Mutable as VUM

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

然后您可以定义一个接口，使所有 public 操作 type-checked length-safe，同时仍保留 MVector.

的性能配置文件

Haskell 中的大小索引可变数组

Size indexed mutable arrays in Haskell

arrays

haskell

dependent-type