我怎样才能拥有一个值严格的向量，就像带有刘海（！）的普通类型？

Question

Haskell 中的一些常见的 性能建议 是使快速数据结构“严格脊柱”，以便结构（但不一定是其内容）在创建时得到充分评估。当我们插入一个值并且该结构位于缓存中时，这让我们可以做更多的工作，而不是推迟它直到我们查找一个值。

对于普通数据类型，例如Data.IntMap

中的二进制 trie，可以通过严格控制数据结构中的相关字段来实现：

data IntMap a = Bin {- ... -} !(IntMap a) !(IntMap a)
              | {- ... -}

（摘自

Data.IntMap.Base

源。）

如果我想将子项存储在向量中而不是直接作为 Bin

的字段，如何实现相同的行为？

data IntMap a = Bin {- ... -} (Vector (IntMap a))
              | {- ... -}

首先，我将回答这个问题的一个简单变体： 如果您的数据类型不可装箱，例如你想要一个严格的

Answer 1

向量， 使用

Data.Vector.Unboxed

。 作为免费的奖励，该实现允许您拥有“数组结构”，

(Vector a, Vector b)

，甚至界面 是不太容易出错的“结构数组”，Vector (a, b)

。
请参阅

有关 AOS 和 SOA 的维基百科

。

但是，在 OP 问题中，我们希望将

IntMap a

---

插入

Vector

，并且

IntMap

 不可拆箱（或可存储或原始）。

各种选择归结为同一个想法：你必须

seq

重视自己。 无论你是为了

Data.Primitive.Array

或者在

Data.Vector.Strict

之上实现自己的 Data.Vector

 （注意：

basicClear

 可以是无操作的，因为
它适用于未装箱的向量，或者您可以使用 

unsafeCoerce ()

 作为虚拟值），
你会

seq

价值观。就是这样

Data.Map.Strict

在顶部实现 与

Data.Map.Lazy

具有相同的惰性结构。

例如

map

Data.Map.Strict

实现为：

map :: (a -> b) -> Map k a -> Map k b
map f = go
  where
    go Tip = Tip
    go (Bin sx kx x l r) = let !x' = f x in Bin sx kx x' (go l) (go r)

与

Data.Map.Lazy.map

比较：

map :: (a -> b) -> Map k a -> Map k b
map f = go where
  go Tip = Tip
  go (Bin sx kx x l r) = Bin sx kx (f x) (go l) (go r)

现在有一个用于此目的的包：

Answer 2

，它在

Data.Strict.Vector 模块中提供严格向量。