-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Dependent finite maps (partial dependent products) -- -- Dependent finite maps (partial dependent products) @package dependent-map @version 0.1 module Data.Dependent.Map -- | Dependent maps: f is a GADT-like thing with a facility for -- rediscovering its type parameter, elements of which function as -- identifiers tagged with the type of the thing they identify. Real -- GADTs are one useful instantiation of f, as are Tags -- from Data.Dependent.Tag. -- -- Semantically, DMap f is equivalent to a set of -- DSum f where no two elements have the same tag. -- -- More informally, DMap is to dependent products as -- M.Map is to (->). Thus it could also be thought -- of as a partial (in the sense of "partial function") dependent -- product. data DMap k -- | A basic dependent sum type; the first component is a tag that -- specifies the type of the second; for example, think of a GADT such -- as: -- --

--   data Tag a where
--      AString :: Tag String
--      AnInt   :: Tag Int
--

-- -- Then, we have the following valid expressions of type DSum -- Tag: -- --

--   AString :=> "hello!"
--   AnInt   :=> 42
--

-- -- And we can write functions that consume DSum Tag values by -- matching, such as: -- --

--   toString :: DSum Tag -> String
--   toString (AString :=> str) = str
--   toString (AnInt   :=> int) = show int
--

-- -- By analogy to the (key => value) construction for dictionary -- entries in many dynamic languages, we use (key :=> value) as the -- constructor for dependent sums. The :=> operator has very low -- precedence and binds to the right, so if the Tag GADT is -- extended with an additional constructor Rec :: Tag (DSum -- Tag), then Rec :=> AnInt :=> 3 + 4 is parsed as -- would be expected (Rec :=> (AnInt :=> (3 + 4))) and has -- type DSum Tag. Its precedence is just above that of $, -- so foo bar $ AString :=> eep is equivalent to -- foo bar (AString :=> eep). data DSum tag :: (* -> *) :: (* -> *) -> * (:=>) :: !tag a -> a -> DSum tag -- | A Key is just a wrapper for the true key type f which -- hides the associated value type and presents the key's GADT-level -- GCompare instance as a vanilla Ord instance so it can be -- used in cases where we don't care about the associated value. data Key f Key :: !f a -> Key f -- | Type class for orderable GADT-like structures. When 2 things are -- equal, must return a witness that their parameter types are equal as -- well (GEQ). |Type class for comparable GADT-like structures. When 2 -- things are equal, must return a witness that their parameter types are -- equal as well (GEQ). class GEq f => GCompare f :: (* -> *) gcompare :: GCompare f => f a -> f b -> GOrdering a b -- | A type for the result of comparing GADT constructors; the type -- parameters of the GADT values being compared are included so that in -- the case where they are equal their parameter types can be unified. data GOrdering a b :: * -> * -> * GLT :: GOrdering a b GEQ :: GOrdering t t GGT :: GOrdering a b -- | O(log n). Find the value at a key. Calls error when the -- element can not be found. -- --

--   fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
--   fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--

(!) :: GCompare k => DMap k -> k v -> v -- | Same as difference. (\\) :: GCompare k => DMap k -> DMap k -> DMap k -- | O(1). Is the map empty? null :: DMap k -> Bool -- | O(1). The number of elements in the map. size :: DMap k -> Int -- | O(log n). Is the key a member of the map? See also -- notMember. member :: GCompare k => k a -> DMap k -> Bool -- | O(log n). Is the key not a member of the map? See also -- member. notMember :: GCompare k => k v -> DMap k -> Bool -- | O(log n). Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. lookup :: GCompare k => k v -> DMap k -> Maybe v -- | O(log n). The expression (findWithDefault def k -- map) returns the value at key k or returns default value -- def when the key is not in the map. findWithDefault :: GCompare k => v -> k v -> DMap k -> v -- | O(1). The empty map. -- --

--   empty      == fromList []
--   size empty == 0
--

empty :: DMap k -- | O(1). A map with a single element. -- --

--   singleton 1 'a'        == fromList [(1, 'a')]
--   size (singleton 1 'a') == 1
--

singleton :: k v -> v -> DMap k -- | O(log n). Insert a new key and value in the map. If the key is -- already present in the map, the associated value is replaced with the -- supplied value. insert is equivalent to insertWith -- const. insert :: GCompare k => k v -> v -> DMap k -> DMap k -- | O(log n). Insert with a function, combining new value and old -- value. insertWith f key value mp will insert the entry -- key :=> value into mp if key does not exist in -- the map. If the key does exist, the function will insert the entry -- key :=> f new_value old_value. insertWith :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k -- | Same as insertWith, but the combining function is applied -- strictly. This is often the most desirable behavior. insertWith' :: GCompare k => (v -> v -> v) -> k v -> v -> DMap k -> DMap k -- | O(log n). Insert with a function, combining key, new value and -- old value. insertWithKey f key value mp will insert -- the entry key :=> value into mp if key does not -- exist in the map. If the key does exist, the function will insert the -- entry key :=> f key new_value old_value. Note that the key -- passed to f is the same key passed to insertWithKey. insertWithKey :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k -- | Same as insertWithKey, but the combining function is applied -- strictly. insertWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k -- | O(log n). Combines insert operation with old value retrieval. -- The expression (insertLookupWithKey f k x map) is a -- pair where the first element is equal to (lookup k -- map) and the second element equal to (insertWithKey f -- k x map). insertLookupWithKey :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k) -- | O(log n). A strict version of insertLookupWithKey. insertLookupWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k) -- | O(log n). Delete a key and its value from the map. When the key -- is not a member of the map, the original map is returned. delete :: GCompare k => k v -> DMap k -> DMap k -- | O(log n). Update a value at a specific key with the result of -- the provided function. When the key is not a member of the map, the -- original map is returned. adjust :: GCompare k => (v -> v) -> k v -> DMap k -> DMap k -- | O(log n). Adjust a value at a specific key. When the key is not -- a member of the map, the original map is returned. adjustWithKey :: GCompare k => (k v -> v -> v) -> k v -> DMap k -> DMap k -- | O(log n). The expression (update f k map) -- updates the value x at k (if it is in the map). If -- (f x) is Nothing, the element is deleted. If it is -- (Just y), the key k is bound to the new value -- y. update :: GCompare k => (v -> Maybe v) -> k v -> DMap k -> DMap k -- | O(log n). The expression (updateWithKey f k -- map) updates the value x at k (if it is in the -- map). If (f k x) is Nothing, the element is deleted. -- If it is (Just y), the key k is bound to the -- new value y. updateWithKey :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap k -- | O(log n). Lookup and update. See also updateWithKey. The -- function returns changed value, if it is updated. Returns the original -- key value if the map entry is deleted. updateLookupWithKey :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> (Maybe v, DMap k) -- | O(log n). The expression (alter f k map) alters -- the value x at k, or absence thereof. alter -- can be used to insert, delete, or update a value in a Map. In -- short : lookup k (alter f k m) = f (lookup k -- m). alter :: GCompare k => (Maybe v -> Maybe v) -> k v -> DMap k -> DMap k -- | O(n+m). The expression (union t1 t2) takes the -- left-biased union of t1 and t2. It prefers -- t1 when duplicate keys are encountered, i.e. -- (union == unionWith const). The -- implementation uses the efficient hedge-union algorithm. -- Hedge-union is more efficient on (bigset `union` smallset). union :: GCompare k => DMap k -> DMap k -> DMap k -- | O(n+m). Union with a combining function. The implementation -- uses the efficient hedge-union algorithm. Hedge-union is more -- efficient on (bigset `union` smallset). unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k -- | The union of a list of maps: (unions == foldl -- union empty). unions :: GCompare k => [DMap k] -> DMap k -- | The union of a list of maps, with a combining operation: -- (unionsWithKey f == foldl (unionWithKey f) -- empty). unionsWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DMap k] -> DMap k -- | O(n+m). Difference of two maps. Return elements of the first -- map not existing in the second map. The implementation uses an -- efficient hedge algorithm comparable with hedge-union. difference :: GCompare k => DMap k -> DMap k -> DMap k -- | O(n+m). Difference with a combining function. When two equal -- keys are encountered, the combining function is applied to the key and -- both values. If it returns Nothing, the element is discarded -- (proper set difference). If it returns (Just y), the -- element is updated with a new value y. The implementation -- uses an efficient hedge algorithm comparable with -- hedge-union. differenceWithKey :: GCompare k => (forall v. k v -> v -> v -> Maybe v) -> DMap k -> DMap k -> DMap k -- | O(n+m). Intersection of two maps. Return data in the first map -- for the keys existing in both maps. (intersection m1 m2 == -- intersectionWith const m1 m2). intersection :: GCompare k => DMap k -> DMap k -> DMap k -- | O(n+m). Intersection with a combining function. Intersection is -- more efficient on (bigset `intersection` smallset). intersectionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k -- | O(n). Map a function over all values in the map. mapWithKey :: (forall v. k v -> v -> v) -> DMap k -> DMap k -- | O(n). The function mapAccumLWithKey threads an -- accumulating argument throught the map in ascending order of keys. mapAccumLWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k) -- | O(n). The function mapAccumRWithKey threads an -- accumulating argument through the map in descending order of keys. mapAccumRWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k) -- | O(n*log n). mapKeysWith c f s is the map -- obtained by applying f to each key of s. -- -- The size of the result may be smaller if f maps two or more -- distinct keys to the same new key. In this case the associated values -- will be combined using c. mapKeysWith :: GCompare k2 => (forall v. k2 v -> v -> v -> v) -> (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2 -- | O(n). mapKeysMonotonic f s == mapKeys f -- s, but works only when f is strictly monotonic. That is, -- for any values x and y, if x < -- y then f x < f y. The precondition is -- not checked. Semi-formally, we have: -- --

--   and [x < y ==> f x < f y | x <- ls, y <- ls] 
--                       ==> mapKeysMonotonic f s == mapKeys f s
--       where ls = keys s
--

-- -- This means that f maps distinct original keys to distinct -- resulting keys. This function has better performance than -- mapKeys. mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2 -- | O(n). Fold the keys and values in the map, such that -- foldWithKey f z == foldr (uncurry f) z . -- toAscList. -- -- This is identical to foldrWithKey, and you should use that one -- instead of this one. This name is kept for backward compatibility. foldWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> b -- | O(n). Post-order fold. The function will be applied from the -- lowest value to the highest. foldrWithKey :: (forall v. k v -> v -> b -> b) -> b -> DMap k -> b -- | O(n). Pre-order fold. The function will be applied from the -- highest value to the lowest. foldlWithKey :: (forall v. b -> k v -> v -> b) -> b -> DMap k -> b -- | O(n). Return all keys of the map in ascending order. -- --

--   keys (fromList [(5,"a"), (3,"b")]) == [3,5]
--   keys empty == []
--

keys :: DMap k -> [Key k] -- | O(n). Return all key/value pairs in the map in ascending key -- order. assocs :: DMap k -> [DSum k] -- | O(n). Convert to a list of key/value pairs. toList :: DMap k -> [DSum k] -- | O(n*log n). Build a map from a list of key/value pairs. See -- also fromAscList. If the list contains more than one value for -- the same key, the last value for the key is retained. fromList :: GCompare k => [DSum k] -> DMap k -- | O(n*log n). Build a map from a list of key/value pairs with a -- combining function. See also fromAscListWithKey. fromListWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k -- | O(n). Convert to an ascending list. toAscList :: DMap k -> [DSum k] -- | O(n). Convert to a descending list. toDescList :: DMap k -> [DSum k] -- | O(n). Build a map from an ascending list in linear time. The -- precondition (input list is ascending) is not checked. fromAscList :: GEq k => [DSum k] -> DMap k -- | O(n). Build a map from an ascending list in linear time with a -- combining function for equal keys. The precondition (input list is -- ascending) is not checked. fromAscListWithKey :: GEq k => (forall v. k v -> v -> v -> v) -> [DSum k] -> DMap k -- | O(n). Build a map from an ascending list of distinct elements -- in linear time. The precondition is not checked. fromDistinctAscList :: [DSum k] -> DMap k -- | filter, applied to a predicate and a list, returns the list of -- those elements that satisfy the predicate; i.e., -- --

--   filter p xs = [ x | x <- xs, p x]
--

filter :: (a -> Bool) -> [a] -> [a] -- | O(n). Filter all keys/values that satisfy the predicate. filterWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> DMap k -- | O(n). Partition the map according to a predicate. The first map -- contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also split. partitionWithKey :: GCompare k => (forall v. k v -> v -> Bool) -> DMap k -> (DMap k, DMap k) -- | O(n). Map keys/values and collect the Just results. mapMaybeWithKey :: GCompare k => (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k -- | O(n). Map keys/values and separate the Left and -- Right results. mapEitherWithKey :: GCompare k => (forall v. k v -> v -> Either v v) -> DMap k -> (DMap k, DMap k) -- | O(log n). The expression (split k map) is a -- pair (map1,map2) where the keys in map1 are smaller -- than k and the keys in map2 larger than k. -- Any key equal to k is found in neither map1 nor -- map2. split :: GCompare k => k v -> DMap k -> (DMap k, DMap k) -- | O(log n). The expression (splitLookup k map) -- splits a map just like split but also returns lookup -- k map. splitLookup :: GCompare k => k v -> DMap k -> (DMap k, Maybe v, DMap k) -- | O(n+m). This function is defined as (isSubmapOf = -- isSubmapOfBy eqTagged)). isSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool -- | O(n+m). The expression (isSubmapOfBy f t1 t2) -- returns True if all keys in t1 are in tree -- t2, and when f returns True when applied to -- their respective keys and values. isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> Bool -- | O(n+m). Is this a proper submap? (ie. a submap but not equal). -- Defined as (isProperSubmapOf = isProperSubmapOfBy -- eqTagged). isProperSubmapOf :: (GCompare k, EqTag k) => DMap k -> DMap k -> Bool -- | O(n+m). Is this a proper submap? (ie. a submap but not equal). -- The expression (isProperSubmapOfBy f m1 m2) returns -- True when m1 and m2 are not equal, all keys -- in m1 are in m2, and when f returns -- True when applied to their respective keys and values. isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> v -> v -> Bool) -> DMap k -> DMap k -> Bool -- | O(log n). Lookup the index of a key. The index is a -- number from 0 up to, but not including, the size of the -- map. lookupIndex :: GCompare k => k v -> DMap k -> Maybe Int -- | O(log n). Return the index of a key. The index is a -- number from 0 up to, but not including, the size of the -- map. Calls error when the key is not a member of the -- map. findIndex :: GCompare k => k v -> DMap k -> Int -- | O(log n). Retrieve an element by index. Calls -- error when an invalid index is used. elemAt :: Int -> DMap k -> DSum k -- | O(log n). Update the element at index. Calls -- error when an invalid index is used. updateAt :: (forall v. k v -> v -> Maybe v) -> Int -> DMap k -> DMap k -- | O(log n). Delete the element at index. Defined as -- (deleteAt i map = updateAt (k x -> -- Nothing) i map). deleteAt :: Int -> DMap k -> DMap k -- | O(log n). The minimal key of the map. Calls error is the -- map is empty. findMin :: DMap k -> DSum k -- | O(log n). The maximal key of the map. Calls error is the -- map is empty. findMax :: DMap k -> DSum k -- | O(log n). Delete the minimal key. Returns an empty map if the -- map is empty. deleteMin :: DMap k -> DMap k -- | O(log n). Delete the maximal key. Returns an empty map if the -- map is empty. deleteMax :: DMap k -> DMap k -- | O(log n). Delete and find the minimal element. -- --

--   deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) 
--   deleteFindMin                                            Error: can not return the minimal element of an empty map
--

deleteFindMin :: DMap k -> (DSum k, DMap k) -- | O(log n). Delete and find the maximal element. -- --

--   deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
--   deleteFindMax empty                                      Error: can not return the maximal element of an empty map
--

deleteFindMax :: DMap k -> (DSum k, DMap k) -- | O(log n). Update the value at the minimal key. updateMinWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k -- | O(log n). Update the value at the maximal key. updateMaxWithKey :: (forall v. k v -> v -> Maybe v) -> DMap k -> DMap k -- | O(log n). Retrieves the minimal (key :=> value) entry of the -- map, and the map stripped of that element, or Nothing if passed -- an empty map. minViewWithKey :: DMap k -> Maybe (DSum k, DMap k) -- | O(log n). Retrieves the maximal (key :=> value) entry of the -- map, and the map stripped of that element, or Nothing if passed -- an empty map. maxViewWithKey :: DMap k -> Maybe (DSum k, DMap k) -- | O(n). Show the tree that implements the map. The tree is shown -- in a compressed, hanging format. See showTreeWith. showTree :: ShowTag k => DMap k -> String -- | O(n). The expression (showTreeWith showelem hang -- wide map) shows the tree that implements the map. Elements are -- shown using the showElem function. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. showTreeWith :: (forall v. k v -> v -> String) -> Bool -> Bool -> DMap k -> String -- | O(n). Test if the internal map structure is valid. valid :: GCompare k => DMap k -> Bool instance Typeable1 f => Typeable (DMap f) instance ShowTag k => Show (DMap k) instance (GCompare f, ReadTag f) => Read (DMap f) instance OrdTag k => Ord (DMap k) instance EqTag k => Eq (DMap k) instance GCompare k => Monoid (DMap k)