How can I have a vector that's strict in its values, like a normal type with bangs (!)?

Question

Some common performance advice in Haskell is to make fast data structures "spine strict" so that the structure, but not necessarily its contents, is fully evaluated as it is created. This lets us do more work when we insert a value and the structure is in cache as opposed to putting it off until we look a value up.

With a normal data type, like the binary trie from Data.IntMap, this can be accomplished by making the relevant fields in the data structure strict:

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

(Excerpt from the Data.IntMap.Base source.)

How can I achieve the same behavior if I want to store the children in a vector rather than directly as fields of Bin?

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

Answer 1

First, I'll answer a simple variant of the question: If your data type is unboxable, e.g. you want a strict vector of Ints, use Data.Vector.Unboxed. As a free bonus, the implementation allows you to have "structure of arrays", (Vector a, Vector b), even the interface is less error-prone "array of structures", Vector (a, b). See Wikipedia on AOS and SOA.

---

Yet, in the OPs question, we want to stick IntMap a into Vector, and IntMap isn't unboxable (or storable or primitive).

The various options boil down to the same idea: you have to seq values yourself. Whether you go for Data.Primitive.Array or implementing own Data.Vector.Strict on top of Data.Vector (note: basicClear can be no-op as it is for unboxed vectors, or you can use unsafeCoerce () as a dummy value), you will seq values. This is how Data.Map.Strict is implemented on top of the same lazy structure as Data.Map.Lazy.

For example map Data.Map.Strict is implemented as:

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)

Compare that to 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)