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)

Methods

fmap :: (a -> b) -> TotalMap k a -> TotalMap k b

(<$) :: a -> TotalMap k b -> TotalMap k a

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

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

Methods

pure :: a -> TotalMap k a

(<*>) :: TotalMap k (a -> b) -> TotalMap k a -> TotalMap k b

(*>) :: TotalMap k a -> TotalMap k b -> TotalMap k b

(<*) :: TotalMap k a -> TotalMap k b -> TotalMap k a

Foldable (TotalMap k)

Methods

fold :: Monoid m => TotalMap k m -> m

foldMap :: Monoid m => (a -> m) -> TotalMap k a -> m

foldr :: (a -> b -> b) -> b -> TotalMap k a -> b

foldr' :: (a -> b -> b) -> b -> TotalMap k a -> b

foldl :: (b -> a -> b) -> b -> TotalMap k a -> b

foldl' :: (b -> a -> b) -> b -> TotalMap k a -> b

foldr1 :: (a -> a -> a) -> TotalMap k a -> a

foldl1 :: (a -> a -> a) -> TotalMap k a -> a

toList :: TotalMap k a -> [a]

null :: TotalMap k a -> Bool

length :: TotalMap k a -> Int

elem :: Eq a => a -> TotalMap k a -> Bool

maximum :: Ord a => TotalMap k a -> a

minimum :: Ord a => TotalMap k a -> a

sum :: Num a => TotalMap k a -> a

product :: Num a => TotalMap k a -> a

Traversable (TotalMap k)

Methods

traverse :: Applicative f => (a -> f b) -> TotalMap k a -> f (TotalMap k b)

sequenceA :: Applicative f => TotalMap k (f a) -> f (TotalMap k a)

mapM :: Monad m => (a -> m b) -> TotalMap k a -> m (TotalMap k b)

sequence :: Monad m => TotalMap k (m a) -> m (TotalMap k a)

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

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

Methods

distribute :: Functor f => f (TotalMap k a) -> TotalMap k (f a)

collect :: Functor f => (a -> TotalMap k b) -> f a -> TotalMap k (f b)

distributeM :: Monad m => m (TotalMap k a) -> TotalMap k (m a)

collectM :: Monad m => (a -> TotalMap k b) -> m a -> TotalMap k (m b)

(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)

Associated Types

type Rep (TotalMap k :: * -> *) :: *

Methods

tabulate :: (Rep (TotalMap k) -> a) -> TotalMap k a

index :: TotalMap k a -> Rep (TotalMap k) -> a

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

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

Methods

serializeWith :: MonadPut m => (a -> m ()) -> TotalMap k a -> m ()

deserializeWith :: MonadGet m => m a -> m (TotalMap k a)

Keyed (TotalMap k)

Methods

mapWithKey :: (Key (TotalMap k) -> a -> b) -> TotalMap k a -> TotalMap k b

Ord k => Zip (TotalMap k)

Methods

zipWith :: (a -> b -> c) -> TotalMap k a -> TotalMap k b -> TotalMap k c

zip :: TotalMap k a -> TotalMap k b -> TotalMap k (a, b)

zap :: TotalMap k (a -> b) -> TotalMap k a -> TotalMap k b

Ord k => ZipWithKey (TotalMap k)

Methods

zipWithKey :: (Key (TotalMap k) -> a -> b -> c) -> TotalMap k a -> TotalMap k b -> TotalMap k c

zapWithKey :: TotalMap k (Key (TotalMap k) -> a -> b) -> TotalMap k a -> TotalMap k b

Ord k => Indexable (TotalMap k)

Methods

index :: TotalMap k a -> Key (TotalMap k) -> a

Ord k => Lookup (TotalMap k)

Methods

lookup :: Key (TotalMap k) -> TotalMap k a -> Maybe a

Ord k => Adjustable (TotalMap k)

Methods

adjust :: (a -> a) -> Key (TotalMap k) -> TotalMap k a -> TotalMap k a

replace :: Key (TotalMap k) -> a -> TotalMap k a -> TotalMap k a

Ord k => FoldableWithKey (TotalMap k)

Methods

toKeyedList :: TotalMap k a -> [(Key (TotalMap k), a)]

foldMapWithKey :: Monoid m => (Key (TotalMap k) -> a -> m) -> TotalMap k a -> m

foldrWithKey :: (Key (TotalMap k) -> a -> b -> b) -> b -> TotalMap k a -> b

foldlWithKey :: (b -> Key (TotalMap k) -> a -> b) -> b -> TotalMap k a -> b

Ord k => TraversableWithKey (TotalMap k)

Complexity: traverseWithKey O(n)

Methods

traverseWithKey :: Applicative f => (Key (TotalMap k) -> a -> f b) -> TotalMap k a -> f (TotalMap k b)

mapWithKeyM :: Monad m => (Key (TotalMap k) -> a -> m b) -> TotalMap k a -> m (TotalMap k b)

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

Complexity: all O(n)

Methods

dot :: Num a => TotalMap k a -> TotalMap k a -> a

quadrance :: Num a => TotalMap k a -> a

qd :: Num a => TotalMap k a -> TotalMap k a -> a

distance :: Floating a => TotalMap k a -> TotalMap k a -> a

norm :: Floating a => TotalMap k a -> a

signorm :: Floating a => TotalMap k a -> TotalMap k a

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

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

Methods

zero :: Num a => TotalMap k a

(^+^) :: Num a => TotalMap k a -> TotalMap k a -> TotalMap k a

(^-^) :: Num a => TotalMap k a -> TotalMap k a -> TotalMap k a

lerp :: Num a => a -> TotalMap k a -> TotalMap k a -> TotalMap k a

liftU2 :: (a -> a -> a) -> TotalMap k a -> TotalMap k a -> TotalMap k a

liftI2 :: (a -> b -> c) -> TotalMap k a -> TotalMap k b -> TotalMap k c

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

Methods

(==) :: TotalMap k a -> TotalMap k a -> Bool

(/=) :: TotalMap k a -> TotalMap k a -> Bool

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

Methods

compare :: TotalMap k a -> TotalMap k a -> Ordering

(<) :: TotalMap k a -> TotalMap k a -> Bool

(<=) :: TotalMap k a -> TotalMap k a -> Bool

(>) :: TotalMap k a -> TotalMap k a -> Bool

(>=) :: TotalMap k a -> TotalMap k a -> Bool

max :: TotalMap k a -> TotalMap k a -> TotalMap k a

min :: TotalMap k a -> TotalMap k a -> TotalMap k a

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

Methods

readsPrec :: Int -> ReadS (TotalMap k a)

readList :: ReadS [TotalMap k a]

readPrec :: ReadPrec (TotalMap k a)

readListPrec :: ReadPrec [TotalMap k a]

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

Methods

showsPrec :: Int -> TotalMap k a -> ShowS

show :: TotalMap k a -> String

showList :: [TotalMap k a] -> ShowS

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

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

Methods

serialize :: MonadPut m => TotalMap k a -> m ()

deserialize :: MonadGet m => m (TotalMap k a)

type Rep (TotalMap k)

type Rep (TotalMap k) = k

type Key (TotalMap k)

type Key (TotalMap k) = k