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 ::  Key x String -> Key x1 Double -> Key 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:

• In the keyLocal example, keys are created locally with the withKey function. The type of the withKey function is (forall x. Key x a -> b) -> b, which means it assigns a key and passes it to the given function. The key cannot escape the function (this would yield a type error). Hence, we say the key is scoped to the function. The scope type argument of the key is then an existential type.
• In the keyGlobal example, keys are created globally with createKey in the IO monad. This allows to create keys that are not not scoped to a single function, but to the whole program. The scope type argument of the key is then T.

This module differs from hackage package hetero-map in the following ways:

• Lookup, insertion and updates are O(log n) when using this module, whereas they are O(n) when using hetero-map.
• With this module we cannot statically ensure that a Heterogenous map has a some key (i.e. (!) might throw error, like in Map). With hetero-map it is possible to statically rule out such errors.
• The interface of this module is more similar to Map.

This module differs from stable-maps in the following ways:

• Key can be created safely without using the IO monad.
• The interface is more uniform and implements more of the Map interface.
• This module uses a Hashmap as a backend, whereas stable-maps uses Data.Map. Hashmaps are faster, see http://blog.johantibell.com/2012/03/announcing-unordered-containers-02.html.

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.