Как я могу получить вектор, строгий по своим значениям, как обычный тип с bangs (!)?

Некоторый общий совет по эффективности в Haskell заключается в том, чтобы быстро создавать структуры данных "spine strict", чтобы структура, но не обязательно ее содержимое, полностью оценивается по мере его создания. Это позволяет нам делать больше работы, когда мы вставляем значение, а структура находится в кеше, а не откладываем его, пока мы не посмотрим на значение вверх.

С обычным типом данных, например двоичным trie из Data.IntMap, это может быть выполнено путем создания соответствующих полей в структуре данных строго:

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

(Выдержка из источника Data.IntMap.Base.)

Как я могу достичь такого же поведения, если я хочу хранить дочерние элементы в векторе, а не непосредственно как поля Bin?

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

Ответы

Ответ 1

Во-первых, я отвечу на простой вариант вопроса: Если ваш тип данных не может быть загружен, например. вам нужен строгий вектор Int s, используйте Data.Vector.Unboxed. В качестве бесплатного бонуса реализация позволяет вам иметь "структуру массивов", (Vector a, Vector b), даже интерфейс менее подвержен ошибкам "массив структур", Vector (a, b). См. Википедия на AOS и SOA.

Тем не менее, в вопросе OPs мы хотим вставить IntMap a в Vector и IntMap не является unboxable (или сохраняемым или примитивным).

Различные варианты сводятся к одной и той же идее: вы должны seq оценивать себя. Если вы идете Data.Primitive.Array или реализовать собственный Data.Vector.Strict поверх Data.Vector (примечание: basicClear может быть не-op как это для распакованных векторов, или вы можете использовать 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)