total-maps-1.0.0.3: Dense and sparse total maps.

Data.Total.Map.Sparse

Description

Sparse, total maps for bounded types.

Synopsis

# Documentation

data TotalSparseMap k a Source #

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

 Source # Methodsfmap :: (a -> b) -> TotalSparseMap k a -> TotalSparseMap k b #(<\$) :: a -> TotalSparseMap k b -> TotalSparseMap k a # Ord k => Applicative (TotalSparseMap k) Source # Zippy applicative. Complexity: pure O(1), <*> O(k1 + k2) Methodspure :: a -> TotalSparseMap k a #(<*>) :: TotalSparseMap k (a -> b) -> TotalSparseMap k a -> TotalSparseMap k b #(*>) :: TotalSparseMap k a -> TotalSparseMap k b -> TotalSparseMap k b #(<*) :: TotalSparseMap k a -> TotalSparseMap k b -> TotalSparseMap k a # (Ord k, Enum k, Bounded k) => Foldable (TotalSparseMap k) Source # 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 Methodsfold :: Monoid m => TotalSparseMap k m -> m #foldMap :: Monoid m => (a -> m) -> TotalSparseMap k a -> m #foldr :: (a -> b -> b) -> b -> TotalSparseMap k a -> b #foldr' :: (a -> b -> b) -> b -> TotalSparseMap k a -> b #foldl :: (b -> a -> b) -> b -> TotalSparseMap k a -> b #foldl' :: (b -> a -> b) -> b -> TotalSparseMap k a -> b #foldr1 :: (a -> a -> a) -> TotalSparseMap k a -> a #foldl1 :: (a -> a -> a) -> TotalSparseMap k a -> a #toList :: TotalSparseMap k a -> [a] #null :: TotalSparseMap k a -> Bool #length :: TotalSparseMap k a -> Int #elem :: Eq a => a -> TotalSparseMap k a -> Bool #maximum :: Ord a => TotalSparseMap k a -> a #minimum :: Ord a => TotalSparseMap k a -> a #sum :: Num a => TotalSparseMap k a -> a #product :: Num a => TotalSparseMap k a -> a # (Ord k, Enum k, Bounded k, Serial k) => Serial1 (TotalSparseMap k) Source # Complexity: serializeWith O(n), deserializeWith O(n) MethodsserializeWith :: MonadPut m => (a -> m ()) -> TotalSparseMap k a -> m () #deserializeWith :: MonadGet m => m a -> m (TotalSparseMap k a) # Ord k => Zip (TotalSparseMap k) Source # Complexity: all O(k1 + k2) MethodszipWith :: (a -> b -> c) -> TotalSparseMap k a -> TotalSparseMap k b -> TotalSparseMap k c #zip :: TotalSparseMap k a -> TotalSparseMap k b -> TotalSparseMap k (a, b) #zap :: TotalSparseMap k (a -> b) -> TotalSparseMap k a -> TotalSparseMap k b # Ord k => Indexable (TotalSparseMap k) Source # Complexity: index O(log k) Methodsindex :: TotalSparseMap k a -> Key (TotalSparseMap k) -> a # Ord k => Lookup (TotalSparseMap k) Source # Complexity: lookup O(log k) Methodslookup :: Key (TotalSparseMap k) -> TotalSparseMap k a -> Maybe a # Ord k => Adjustable (TotalSparseMap k) Source # Complexity: all O(log k) Methodsadjust :: (a -> a) -> Key (TotalSparseMap k) -> TotalSparseMap k a -> TotalSparseMap k a #replace :: Key (TotalSparseMap k) -> a -> TotalSparseMap k a -> TotalSparseMap k a # (Ord k, Enum k, Bounded k) => Metric (TotalSparseMap k) Source # Complexity: all O(k * log (n/k)) - arises from fold Methodsdot :: Num a => TotalSparseMap k a -> TotalSparseMap k a -> a #quadrance :: Num a => TotalSparseMap k a -> a #qd :: Num a => TotalSparseMap k a -> TotalSparseMap k a -> a #distance :: Floating a => TotalSparseMap k a -> TotalSparseMap k a -> a #norm :: Floating a => TotalSparseMap k a -> a #signorm :: Floating a => TotalSparseMap k a -> TotalSparseMap k a # Ord k => Additive (TotalSparseMap k) Source # Complexity: zero O(1), rest O(k1 + k2) Methodszero :: Num a => TotalSparseMap k a #(^+^) :: Num a => TotalSparseMap k a -> TotalSparseMap k a -> TotalSparseMap k a #(^-^) :: Num a => TotalSparseMap k a -> TotalSparseMap k a -> TotalSparseMap k a #lerp :: Num a => a -> TotalSparseMap k a -> TotalSparseMap k a -> TotalSparseMap k a #liftU2 :: (a -> a -> a) -> TotalSparseMap k a -> TotalSparseMap k a -> TotalSparseMap k a #liftI2 :: (a -> b -> c) -> TotalSparseMap k a -> TotalSparseMap k b -> TotalSparseMap k c # (Ord k, Enum k, Bounded k, Eq a) => Eq (TotalSparseMap k a) Source # Complexity: O(k * log (n/k)) - arises from fold Methods(==) :: TotalSparseMap k a -> TotalSparseMap k a -> Bool #(/=) :: TotalSparseMap k a -> TotalSparseMap k a -> Bool # (Ord k, Enum k, Bounded k, Ord a) => Ord (TotalSparseMap k a) Source # Complexity: O(k * log (n/k)) - arises from fold Methodscompare :: TotalSparseMap k a -> TotalSparseMap k a -> Ordering #(<) :: TotalSparseMap k a -> TotalSparseMap k a -> Bool #(<=) :: TotalSparseMap k a -> TotalSparseMap k a -> Bool #(>) :: TotalSparseMap k a -> TotalSparseMap k a -> Bool #(>=) :: TotalSparseMap k a -> TotalSparseMap k a -> Bool #max :: TotalSparseMap k a -> TotalSparseMap k a -> TotalSparseMap k a #min :: TotalSparseMap k a -> TotalSparseMap k a -> TotalSparseMap k a # (Read a, Read k, Ord k) => Read (TotalSparseMap k a) Source # MethodsreadsPrec :: Int -> ReadS (TotalSparseMap k a) #readList :: ReadS [TotalSparseMap k a] # (Show a, Show k) => Show (TotalSparseMap k a) Source # MethodsshowsPrec :: Int -> TotalSparseMap k a -> ShowS #show :: TotalSparseMap k a -> String #showList :: [TotalSparseMap k a] -> ShowS # (Ord k, Enum k, Bounded k, Serial k, Serial a) => Serial (TotalSparseMap k a) Source # Complexity: serialize O(n), deserialize O(n) Methodsserialize :: MonadPut m => TotalSparseMap k a -> m () #deserialize :: MonadGet m => m (TotalSparseMap k a) # type Key (TotalSparseMap k) Source # type Key (TotalSparseMap k) = k

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

Convert the sparse map to a dense one.

Complexity: O(n * log n)