Data.Total.Map

Dense, total, maps for bounded types.

Documentation

newtype TotalMap k a

A total map from keys k to values a.

Most functions are derived from Map.

n is equal to the number of keys.

Unfortunately I cannot find any law linking Enum with Ord, so we cannot be sure that [minBound .. maxBound] is sorted. Because of that functions like pure and tabulate have complexity O(n * log n), while they could be O(n).

Constructors

TotalMap (Map k a)

Instances

Functor (TotalMap k)

(Ord k, Enum k, Bounded k) => Applicative (TotalMap k)

Zippy applicative. Complexity: pure O(n * log n), <*> O(n).

Foldable (TotalMap k)

Traversable (TotalMap k)

(Ord k, Enum k, Bounded k) => Distributive (TotalMap k)

Complexity: distribute O(n * log n + n * fmap)

(Ord k, Enum k, Bounded k) => Representable (TotalMap k)

Convert from and to a (k -> a) function.

Complexity: tabulate O(n * log n), index O(log n)

(Ord k, Enum k, Bounded k) => Serial1 (TotalMap k)

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

Keyed (TotalMap k)

Ord k => Zip (TotalMap k)

Ord k => ZipWithKey (TotalMap k)

Ord k => Indexable (TotalMap k)

Ord k => Lookup (TotalMap k)

Ord k => Adjustable (TotalMap k)

Ord k => FoldableWithKey (TotalMap k)

Ord k => TraversableWithKey (TotalMap k)

Complexity: traverseWithKey O(n)

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

Complexity: all O(n)

(Ord k, Enum k, Bounded k) => Additive (TotalMap k)

Complexity: zero O(n * log n), rest O(n)

(Eq k, Eq a) => Eq (TotalMap k a)

(Ord k, Ord a) => Ord (TotalMap k a)

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

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

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

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

type Rep (TotalMap k) = k

type Key (TotalMap k) = k