Cleff.Internal.Vec

This module contains an efficient vector datatype that is implemented as a radix tree.

This is an internal module and its API may change even between minor versions. Therefore you should be extra careful if you're to depend on this module.

Documentation

data Vec a

An efficient vector type, implemented as a radix tree. It has the following time complexities:

• Lookup: \( O(\log n) \)
• Update: \( O(\log n) \)
• Append: \( O(\log n) \)

The branching factor (base of log) is 32 therefore the time is close to constant in most cases. Note that in practice, lookup is faster than update, and update is faster than append.

empty :: Vec a

The empty Vec.

lookup :: Int -> Vec a -> a

Lookup in a Vec by an index. This does not perform any bounds check.

update :: Int -> a -> Vec a -> Vec a

Update a value in a Vec by an index. The value will be forced before installing. This does not perform any bounds check.

snoc :: Vec a -> a -> Vec a

Append a value to a Vec. The value will be forced before installing. This does not perform any bounds check.