-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Fast heterogeneous maps and unconstrained typeable like functionality. -- @package HMap @version 1.2.3 -- | Provides a Typeable-like interface for things that cannot derive -- typeable. module Data.Untypeable data Untypeable -- | Make an Untypeable value inject :: HKey s a -> a -> Untypeable -- | Project (i.e. cast) an untypeable value with a given key. project :: HKey s a -> Untypeable -> Maybe a module Data.HKey -- | The datatype of Keys. -- -- -- -- For example, Key T Int is a top-level key that can be used to -- store values of type Int in a heterogenous map. data HKey s a -- | O(1). Scopes a key to the given function The key cannot escape -- the function (because of the existential type). -- -- The implementation actually *creates* a key, but because the key -- cannot escape the given function f, there is no way to -- observe that if we run withKey f twice, that it will get a -- different key the second time. withKey :: (forall x. HKey x a -> b) -> b -- | The scope of top-level keys. data T -- | O(1). Create a new top-level key. createKey :: IO (HKey T a) -- | A monad that can be used to create keys Keys cannot escape the monad, -- analogous to the ST Monad. Can be used instead of the withKey -- function if you need an statically unknown number of keys. -- -- The applicative instance is more non-strict than the standard -- ap: -- -- let hang = getKey >> hang in snd $ runIdentity $ runKeyT $ pure -- (,) * hang * (getKey >> return 2) does not hang, -- but with ap it does. type KeyM s a = KeyT s Identity a data KeyT s m a type Key s = KeyT s Identity runKey :: (forall s. Key s a) -> a -- | Obtain a key in the key monad newKey :: KeyT s m (HKey s a) -- | Obtain a key in the key monad, alias for newKey getKey :: KeyT s m (HKey s a) -- | Split of a keyT computation. -- -- As an analogy, think of a random number generator some random number -- generator can be split, from one random number generator we obtain two -- distinct random number generator that are unrelated. -- -- The KeyT monad gives us access to a name source, this operation allows -- us to split the name source. The generated name from both this and the -- split off computation have the same scope, but are otherwise -- underlated. -- -- Notice that the sharing of the same scope is not a problem because the -- monad ensures referential transparency. keyTSplit :: KeyT s m a -> KeyT s m (m a) -- | Run a key monad. Existential type makes sure keys cannot escape. runKeyT :: Monad m => (forall s. KeyT s m a) -> m a -- | An efficient implementation of heterogeneous maps. -- -- A heterogeneous map can store values of different types. This in -- contrast to a homogenous map (such as the one in Map) which can -- store values of a single type. -- -- For example, here we use a map with String (name), -- Double (salary) and Bool (female): -- -- 
--   import Data.HMap 
--   
--   -- type can be inferred.
--   example :: HKey x String -> HKey x1 Double -> HKey x2 Bool 
--              -> String
--   example name salary female = 
--     format a ++ "\n" ++ format b ++ "\n"
--     where a = insert name "Edsger" $ 
--               insert salary 4450.0 $ 
--               insert female False empty
--           b = insert name "Ada"    $ 
--               insert salary 5000.0 $ 
--               insert female True empty
--           format x = x ! name ++ 
--                      ": salary=" ++ show (x ! salary) ++ 
--                      ", female="  ++ show (x ! female)
--   
--   keyLocal :: String
--   keyLocal = withKey $ withKey $ withKey example
--   
--   keyGlobal :: IO String
--   keyGlobal = 
--     do name   <- createKey
--        salary <- createKey
--        female <- createKey
--        return $ example name salary female
--                       
--   main = do print "local"
--             putStr keyLocal
--             print "global"
--             keyGlobal >>= putStr
--
-- -- Which gives: -- -- 
--   "local"
--   Edsger: salary=4450.0, female=False
--   Ada: salary=5000.0, female=True
--   "global"
--   Edsger: salary=4450.0, female=False
--   Ada: salary=5000.0, female=True
--
-- -- Key types carry two type arguments: the scope of the key and the the -- type of things that can be stored at this key, for example -- String or Int. -- -- The scope of the key depends on how it is created: -- -- -- -- This module differs from hackage package hetero-map in the -- following ways: -- -- -- -- This module differs from stable-maps in the following ways: -- -- -- -- Another difference to both packages is that HMap has better memory -- performance in the following way: An entry into an HMap does not keep -- the value alive if the key is not alive. After all, if the key is -- dead, then there is no way to retrieve the value! -- -- Hence, a HMap can have elements which can never be accessed again. Use -- the IO operation purge to remove these. -- -- Since many function names (but not the type name) clash with -- Prelude names, this module is usually imported -- qualified, e.g. -- -- 
--   import Data.HMap (HMap)
--   import qualified Data.HMap as HMap
--
-- -- This module uses Data.HashMap.Lazy as a backend. Every -- function from Map that makes sense in a heterogenous setting -- has been implemented. -- -- Note that the implementation is left-biased -- the elements of -- a first argument are always preferred to the second, for example in -- union or insert. -- -- Operation comments contain the operation time complexity in the Big-O -- notation http://en.wikipedia.org/wiki/Big_O_notation. module Data.HMap -- | The type of hetrogenous maps. data HMap -- | O(log n). Find the value at a key. Calls error when the -- element can not be found. (!) :: HMap -> HKey x a -> a -- | Same as difference. (\\) :: HMap -> HMap -> HMap -- | O(1). Is the map empty? null :: HMap -> Bool -- | O(1). The number of elements in the map. size :: HMap -> Int -- | O(log n). Is the key a member of the map? See also -- notMember. member :: HKey x a -> HMap -> Bool -- | O(log n). Is the key not a member of the map? See also -- member. notMember :: HKey x a -> HMap -> 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 :: HKey x a -> HMap -> Maybe a -- | 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 :: a -> HKey x a -> HMap -> a -- | O(1). The empty map. empty :: HMap -- | O(1). A map with a single element. singleton :: HKey x a -> a -> HMap -- | 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 :: HKey s a -> a -> HMap -> HMap -- | O(log n). Insert with a function, combining new value and old -- value. insertWith f key value mp will insert the pair -- (key, value) into mp if key does not exist in the map. If the -- key does exist, the function will insert the pair (key, f -- new_value old_value). insertWith :: (a -> a -> a) -> HKey x a -> a -> HMap -> HMap -- | 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 :: HKey x a -> HMap -> HMap -- | 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 :: (a -> a) -> HKey x a -> HMap -> HMap -- | 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 :: (a -> Maybe a) -> HKey x a -> HMap -> HMap -- | 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 :: (Maybe a -> Maybe a) -> HKey x a -> HMap -> HMap -- | 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. union :: HMap -> HMap -> HMap -- | The union of a list of maps: (unions == foldl -- union empty). unions :: [HMap] -> HMap -- | O(n+m). Difference of two maps. Return elements of the first -- map not existing in the second map. difference :: HMap -> HMap -> HMap -- | O(n+m). Intersection of two maps. Return data in the first map -- for the keys existing in both maps. intersection :: HMap -> HMap -> HMap -- | O(n). Remove dead values from map. -- -- An entry into an HMap does not keep the value alive if the key is not -- alive. After all, if the key is dead, then there is no way to retrieve -- the value! -- -- Hence, a HMap can have elements which can never be accessed again. -- This operation purges such elements from the given map. Notice that -- this does change the size of the map and is hence in the IO monad. purge :: HMap -> IO HMap -- | A set of HKeys module Data.HKeySet -- | The type of hetrogenous key sets. data HKeySet -- | O(1) Construct an empty key set. empty :: HKeySet -- | O(1) Construct a set with a single element. singleton :: HKey s a -> HKeySet -- | O(n+m) Construct a key set containing all elements from both -- sets. -- -- To obtain good performance, the smaller set must be presented as the -- first argument. union :: HKeySet -> HKeySet -> HKeySet -- | Construct a key set containing all elements from a list of key sets. unions :: [HKeySet] -> HKeySet -- | O(1) Return True if this key set is empty, False -- otherwise. null :: HKeySet -> Bool -- | O(n) Return the number of elements in this set. size :: HKeySet -> Int -- | O(min(n,W)) Return True if the given value is present in -- this set, False otherwise. member :: HKey s a -> HKeySet -> Bool -- | O(min(n,W)) Add the specified value to this set. insert :: HKey x a -> HKeySet -> HKeySet -- | O(min(n,W)) Remove the specified value from this set if -- present. delete :: HKey s a -> HKeySet -> HKeySet -- | O(n) Difference of two sets. Return elements of the first set -- not existing in the second. difference :: HKeySet -> HKeySet -> HKeySet -- | O(n) Intersection of two sets. Return elements present in both -- the first set and the second. intersection :: HKeySet -> HKeySet -> HKeySet -- | O(n). Does the map carry any of the keys? overlap :: HMap -> HKeySet -> Bool -- | O(n). Do the keyset and the map have the same keys? sameKeys :: HMap -> HKeySet -> Bool -- | O(n). Remove the keys from the keyset from the map. removeKeys :: HMap -> HKeySet -> HMap