Data.Total.Map.Sparse

Sparse, total maps for bounded types.

Documentation

data TotalSparseMap k a

A total sparse map from keys k to values a. This map is implemented as a partial map and a default value. pure creates an all-default values map with the given default value.

n is equal to the number of keys, k is the number of non-default values. If there are two maps involved k is taken to be the number of non-default values of their union.

Constructors

TotalSparseMap (Map k a) a

Instances

Functor (TotalSparseMap k)

Ord k => Applicative (TotalSparseMap k)

Zippy applicative. Complexity: pure O(1), <*> O(k1 + k2)

(Ord k, Enum k, Bounded k) => Foldable (TotalSparseMap k)

Folds over the whole domain, including the default values.

>>> sum (pure 1 :: TotalSparseMap Int Integer)
18446744073709551616

Complexity: foldMap O(k * log (n/k)), the rest are defined using foldMap

(Ord k, Enum k, Bounded k, Serial k) => Serial1 (TotalSparseMap k)

Complexity: serializeWith O(n), deserializeWith O(n)

Ord k => Zip (TotalSparseMap k)

Complexity: all O(k1 + k2)

Ord k => Indexable (TotalSparseMap k)

Complexity: index O(log k)

Ord k => Lookup (TotalSparseMap k)

Complexity: lookup O(log k)

Ord k => Adjustable (TotalSparseMap k)

Complexity: all O(log k)

(Ord k, Enum k, Bounded k) => Metric (TotalSparseMap k)

Complexity: all O(k * log (n/k)) - arises from fold

Ord k => Additive (TotalSparseMap k)

Complexity: zero O(1), rest O(k1 + k2)

(Ord k, Enum k, Bounded k, Eq a) => Eq (TotalSparseMap k a)

Complexity: O(k * log (n/k)) - arises from fold

(Ord k, Enum k, Bounded k, Ord a) => Ord (TotalSparseMap k a)

Complexity: O(k * log (n/k)) - arises from fold

(Ord k, Read k, Read a) => Read (TotalSparseMap k a)

(Show k, Show a) => Show (TotalSparseMap k a)

(Ord k, Enum k, Bounded k, Serial k, Serial a) => Serial (TotalSparseMap k a)

Complexity: serialize O(n), deserialize O(n)

type Key (TotalSparseMap k) = k

toDenseMap :: (Ord k, Enum k, Bounded k) => TotalSparseMap k a -> TotalMap k a

Convert the sparse map to a dense one.

Complexity: O(n * log n)