haskell - 我怎样才能拥有一个值严格的向量，比如带有刘海(!)的普通类型？

Question

一些常见的performance advice在 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

首先，我将回答问题的一个简单变体:
如果您的数据类型不可装箱，例如你想要 Int 的严格向量年代，
使用 Data.Vector.Unboxed .
作为免费奖励，该实现允许您拥有“数组结构”，(Vector a, Vector b) , 连界面
不易出错的“结构数组”，Vector (a, b) .
见 Wikipedia on AOS and SOA .

然而，在 OPs 问题中，我们想坚持 IntMap a进入 Vector ， 和IntMap不可拆箱(或可存储或原始)。

各种选项归结为同一个想法:您必须 seq重视自己。
无论你去
Data.Primitive.Array
或实现自己的Data.Vector.Strict在 Data.Vector 之上(注意:basicClear 可以为空操作
它用于未装箱的向量，或者您可以使用 unsafeCoerce ()作为一个虚拟值)，
你会seq值(value)观。这是如何
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)