packages feed

unordered-containers (empty) → 0.1.0.0

raw patch · 14 files changed

+1437/−0 lines, 14 filesdep +basedep +deepseqdep +hashablesetup-changed

Dependencies added: base, deepseq, hashable

Files

+ Data/FullList/Lazy.hs view
@@ -0,0 +1,237 @@+{-# LANGUAGE BangPatterns, CPP #-}++------------------------------------------------------------------------+-- |+-- Module      :  Data.FullList.Lazy+-- Copyright   :  2010-2011 Johan Tibell+-- License     :  BSD-style+-- Maintainer  :  johan.tibell@gmail.com+-- Stability   :  provisional+-- Portability :  portable+--+-- Non-empty lists of key/value pairs.  The lists are strict in the+-- keys and lazy in the values.++module Data.FullList.Lazy+    ( FullList(..)+    , List(..)++      -- * Basic interface+    , size+    , singleton+    , lookup+    , insert+    , delete+    , insertWith++      -- * Transformations+    , map++      -- * Folds+    , foldlWithKey'+    , foldrWithKey++      -- * Filter+    , filterWithKey+    ) where++import Control.DeepSeq (NFData(rnf))+import Prelude hiding (lookup, map)++------------------------------------------------------------------------+-- * The 'FullList' type++-- The 'FullList' type has two benefits:+--+--  * it is guaranteed to be non-empty, and+--+--  * it can be unpacked into a data constructor.++-- Invariant: the same key only appears once in a 'FullList'.++-- | A non-empty list of key/value pairs.+data FullList k v = FL !k v !(List k v)+                  deriving Show++instance (Eq k, Eq v) => Eq (FullList k v) where+    (FL k1 v1 xs) == (FL k2 v2 ys) = k1 == k2 && v1 == v2 && xs == ys+    (FL k1 v1 xs) /= (FL k2 v2 ys) = k1 /= k2 || v1 /= v2 || xs /= ys++instance (NFData k, NFData v) => NFData (FullList k v)++data List k v = Nil | Cons !k v !(List k v)+              deriving Show++instance (Eq k, Eq v) => Eq (List k v) where+    (Cons k1 v1 xs) == (Cons k2 v2 ys) = k1 == k2 && v1 == v2 && xs == ys+    Nil == Nil = True+    _   == _   = False++    (Cons k1 v1 xs) /= (Cons k2 v2 ys) = k1 /= k2 || v1 /= v2 || xs /= ys+    Nil /= Nil = False+    _   /= _   = True++instance (NFData k, NFData v) => NFData (List k v) where+    rnf Nil           = ()+    rnf (Cons k v xs) = rnf k `seq` rnf v `seq` rnf xs++-- TODO: Check if evaluation is forced.++------------------------------------------------------------------------+-- * FullList++-- The 'List' functions are not inlined as they should be seldomly+-- called in practice (i.e. we expect few collisions.)++size :: FullList k v -> Int+size (FL _ _ xs) = 1 + sizeL xs++sizeL :: List k v -> Int+sizeL Nil = 0+sizeL (Cons _ _ xs) = 1 + sizeL xs++singleton :: k -> v -> FullList k v+singleton k v = FL k v Nil++lookup :: Eq k => k -> FullList k v -> Maybe v+lookup !k (FL k' v xs)+    | k == k'   = Just v+    | otherwise = lookupL k xs+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE lookup #-}+#endif++lookupL :: Eq k => k -> List k v -> Maybe v+lookupL = go+  where+    go !_ Nil = Nothing+    go k (Cons k' v xs)+        | k == k'   = Just v+        | otherwise = go k xs+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE lookupL #-}+#endif++insert :: Eq k => k -> v -> FullList k v -> FullList k v+insert !k v (FL k' v' xs)+    | k == k'   = FL k v xs+    | otherwise = FL k' v' (insertL k v xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insert #-}+#endif++-- | /O(n)/ Insert at the head of the list to avoid copying the whole+-- list.+insertL :: Eq k => k -> v -> List k v -> List k v+insertL = go+  where+    go !k v Nil = Cons k v Nil+    go k v (Cons k' v' xs)+        | k == k'   = Cons k v xs+        | otherwise = Cons k' v' (go k v xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertL #-}+#endif++delete :: Eq k => k -> FullList k v -> Maybe (FullList k v)+delete !k (FL k' v xs)+    | k == k'   = case xs of+        Nil             -> Nothing+        Cons k'' v' xs' -> Just $ FL k'' v' xs'+    | otherwise = let ys = deleteL k xs+                  in ys `seq` Just (FL k' v ys)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE delete #-}+#endif++deleteL :: Eq k => k -> List k v -> List k v+deleteL = go+  where+    go !_ Nil = Nil+    go k (Cons k' v xs)+        | k == k'   = xs+        | otherwise = Cons k' v (go k xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE deleteL #-}+#endif++insertWith :: Eq k => (v -> v -> v) -> k -> v -> FullList k v -> FullList k v+insertWith f !k v (FL k' v' xs)+    | k == k'   = FL k (f v v') xs+    | otherwise = FL k' v' (insertWithL f k v xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertWith #-}+#endif++insertWithL :: Eq k => (v -> v -> v) -> k -> v -> List k v -> List k v+insertWithL = go+  where+    go _ !k v Nil = Cons k v Nil+    go f k v (Cons k' v' xs)+        | k == k'   = Cons k (f v v') xs+        | otherwise = Cons k' v' (go f k v xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertWithL #-}+#endif++------------------------------------------------------------------------+-- * Transformations++map :: (k1 -> v1 -> (k2, v2)) -> FullList k1 v1 -> FullList k2 v2+map f (FL k v xs) = let (k', v') = f k v+                    in FL k' v' (mapL f xs)+{-# INLINE map #-}++mapL :: (k1 -> v1 -> (k2, v2)) -> List k1 v1 -> List k2 v2+mapL f = go+  where+    go Nil = Nil+    go (Cons k v xs) = let (k', v') = f k v+                       in Cons k' v' (go xs)+{-# INLINE mapL #-}++------------------------------------------------------------------------+-- * Folds++foldlWithKey' :: (a -> k -> v -> a) -> a -> FullList k v -> a+foldlWithKey' f !z (FL k v xs) = foldlWithKey'L f (f z k v) xs+{-# INLINE foldlWithKey' #-}++foldlWithKey'L :: (a -> k -> v -> a) -> a -> List k v -> a+foldlWithKey'L f = go+  where+    go !z Nil          = z+    go z (Cons k v xs) = go (f z k v) xs+{-# INLINE foldlWithKey'L #-}++foldrWithKey :: (k -> v -> a -> a) -> a -> FullList k v -> a+foldrWithKey f z (FL k v xs) = f k v (foldrWithKeyL f z xs)+{-# INLINE foldrWithKey #-}++foldrWithKeyL :: (k -> v -> a -> a) -> a -> List k v -> a+foldrWithKeyL f = go+  where+    go z Nil = z+    go z (Cons k v xs) = f k v (go z xs)+{-# INLINE foldrWithKeyL #-}++------------------------------------------------------------------------+-- * Filter++filterWithKey :: (k -> v -> Bool) -> FullList k v -> Maybe (FullList k v)+filterWithKey p (FL k v xs)+    | p k v     = Just (FL k v ys)+    | otherwise = case ys of+        Nil           -> Nothing+        Cons k' v' zs -> Just $ FL k' v' zs+  where !ys = filterWithKeyL p xs+{-# INLINE filterWithKey #-}++filterWithKeyL :: (k -> v -> Bool) -> List k v -> List k v+filterWithKeyL p = go+  where+    go Nil = Nil+    go (Cons k v xs)+        | p k v     = Cons k v (go xs)+        | otherwise = go xs+{-# INLINE filterWithKeyL #-}
+ Data/FullList/Strict.hs view
@@ -0,0 +1,74 @@+{-# LANGUAGE BangPatterns, CPP #-}++------------------------------------------------------------------------+-- |+-- Module      :  Data.FullList.Strict+-- Copyright   :  2010-2011 Johan Tibell+-- License     :  BSD-style+-- Maintainer  :  johan.tibell@gmail.com+-- Stability   :  provisional+-- Portability :  portable+--+-- Non-empty lists of key/value pairs.  The lists are strict in the+-- keys and the values.++module Data.FullList.Strict+    ( FullList++      -- * Basic interface+    , size+    , singleton+    , lookup+    , insert+    , delete+    , insertWith++      -- * Transformations+    , map++      -- * Folds+    , foldlWithKey'+    , foldrWithKey++      -- * Filter+    , filterWithKey+    ) where++import Prelude hiding (lookup, map)++import Data.FullList.Lazy hiding (insertWith, map)++insertWith :: Eq k => (v -> v -> v) -> k -> v -> FullList k v -> FullList k v+insertWith f !k v (FL k' v' xs)+    | k == k'   = let v'' = f v v' in v'' `seq` FL k v'' xs+    | otherwise = FL k' v' (insertWithL f k v xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertWith #-}+#endif++insertWithL :: Eq k => (v -> v -> v) -> k -> v -> List k v -> List k v+insertWithL = go+  where+    go _ !k v Nil = Cons k v Nil+    go f k v (Cons k' v' xs)+        | k == k'   = let v'' = f v v' in v'' `seq` Cons k v'' xs+        | otherwise = Cons k' v' (go f k v xs)+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertWithL #-}+#endif++------------------------------------------------------------------------+-- * Transformations++map :: (k1 -> v1 -> (k2, v2)) -> FullList k1 v1 -> FullList k2 v2+map f (FL k v xs) = let !(k', !v') = f k v+                    in FL k' v' (mapL f xs)+{-# INLINE map #-}++mapL :: (k1 -> v1 -> (k2, v2)) -> List k1 v1 -> List k2 v2+mapL f = go+  where+    go Nil = Nil+    go (Cons k v xs) = let !(k', !v') = f k v+                       in Cons k' v' (go xs)+{-# INLINE mapL #-}
+ Data/HashMap/Common.hs view
@@ -0,0 +1,171 @@+{-# LANGUAGE BangPatterns, CPP #-}++-- | Code shared between the lazy and strict versions.++module Data.HashMap.Common+    (+      -- * Types+      HashMap(..)+    , Prefix+    , Mask+    , Hash++      -- * Helpers+    , join+    , bin+    , zero+    , nomatch+    , mask+    , maskW+    , branchMask+    , highBit+    ) where++#include "MachDeps.h"++import Control.DeepSeq (NFData(rnf))+import Data.Bits ((.&.), (.|.), complement, shiftR, xor)+import qualified Data.Foldable as Foldable+import Data.Word (Word)+import Prelude hiding (foldr, map)++import qualified Data.FullList.Lazy as FL++------------------------------------------------------------------------+-- * The 'HashMap' type++-- | A map from keys to values.  A map cannot contain duplicate keys;+-- each key can map to at most one value.+data HashMap k v+    = Nil+    | Tip {-# UNPACK #-} !Hash+          {-# UNPACK #-} !(FL.FullList k v)+    | Bin {-# UNPACK #-} !Prefix+          {-# UNPACK #-} !Mask+          !(HashMap k v)+          !(HashMap k v)+    deriving Show++type Prefix = Int+type Mask   = Int+type Hash   = Int++------------------------------------------------------------------------+-- * Instances++-- Since both the lazy and the strict API shares one data type we can+-- only provide one set of instances.  We provide the lazy ones.++instance (Eq k, Eq v) => Eq (HashMap k v) where+    t1 == t2 = equal t1 t2+    t1 /= t2 = nequal t1 t2++equal :: (Eq k, Eq v) => HashMap k v -> HashMap k v -> Bool+equal (Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2) =+    (m1 == m2) && (p1 == p2) && (equal l1 l2) && (equal r1 r2)+equal (Tip h1 l1) (Tip h2 l2) = (h1 == h2) && (l1 == l2)+equal Nil Nil = True+equal _   _   = False++nequal :: (Eq k, Eq v) => HashMap k v -> HashMap k v -> Bool+nequal (Bin p1 m1 l1 r1) (Bin p2 m2 l2 r2) =+    (m1 /= m2) || (p1 /= p2) || (nequal l1 l2) || (nequal r1 r2)+nequal (Tip h1 l1) (Tip h2 l2) = (h1 /= h2) || (l1 /= l2)+nequal Nil Nil = False+nequal _   _   = True++instance (NFData k, NFData v) => NFData (HashMap k v) where+    rnf Nil           = ()+    rnf (Tip _ xs)    = rnf xs+    rnf (Bin _ _ l r) = rnf l `seq` rnf r `seq` ()++instance Functor (HashMap k) where+    fmap = map++-- | /O(n)/ Transform this map by applying a function to every value.+map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2+map f = go+  where+    go (Bin p m l r) = Bin p m (go l) (go r)+    go (Tip h l)     = Tip h (FL.map f' l)+    go Nil           = Nil+    f' k v = (k, f v)+{-# INLINE map #-}++instance Foldable.Foldable (HashMap k) where+    foldr f = foldrWithKey (const f)++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a+foldrWithKey f = go+  where+    go z (Bin _ _ l r) = go (go z r) l+    go z (Tip _ l)     = FL.foldrWithKey f z l+    go z Nil           = z+{-# INLINE foldrWithKey #-}++------------------------------------------------------------------------+-- Helpers++join :: Prefix -> HashMap k v -> Prefix -> HashMap k v -> HashMap k v+join p1 t1 p2 t2+    | zero p1 m = Bin p m t1 t2+    | otherwise = Bin p m t2 t1+  where+    m = branchMask p1 p2+    p = mask p1 m+{-# INLINE join #-}++-- | @bin@ assures that we never have empty trees within a tree.+bin :: Prefix -> Mask -> HashMap k v -> HashMap k v -> HashMap k v+bin _ _ l Nil = l+bin _ _ Nil r = r+bin p m l r   = Bin p m l r+{-# INLINE bin #-}++------------------------------------------------------------------------+-- Endian independent bit twiddling++zero :: Hash -> Mask -> Bool+zero i m = (fromIntegral i :: Word) .&. (fromIntegral m :: Word) == 0+{-# INLINE zero #-}++nomatch :: Hash -> Prefix -> Mask -> Bool+nomatch i p m = (mask i m) /= p+{-# INLINE nomatch #-}++mask :: Hash -> Mask -> Prefix+mask i m = maskW (fromIntegral i :: Word) (fromIntegral m :: Word)+{-# INLINE mask #-}++------------------------------------------------------------------------+-- Big endian operations++maskW :: Word -> Word -> Prefix+maskW i m = fromIntegral (i .&. (complement (m-1) `xor` m))+{-# INLINE maskW #-}++branchMask :: Prefix -> Prefix -> Mask+branchMask p1 p2 =+    fromIntegral (highBit (fromIntegral p1 `xor` fromIntegral p2 :: Word))+{-# INLINE branchMask #-}++-- | Return a 'Word' where only the highest bit is set.+highBit :: Word -> Word+highBit x0 =+    let !x1 = x0 .|. shiftR x0 1+        !x2 = x1 .|. shiftR x1 2+        !x3 = x2 .|. shiftR x2 4+        !x4 = x3 .|. shiftR x3 8+        !x5 = x4 .|. shiftR x4 16+#if WORD_SIZE_IN_BITS == 32+    in x5 `xor` (shiftR x5 1)+#elif WORD_SIZE_IN_BITS == 64+        !x6 = x5 .|. shiftR x5 32+    in x6 `xor` (shiftR x6 1)+#else+# error WORD_SIZE_IN_BITS not supported+#endif+{-# INLINE highBit #-}
+ Data/HashMap/Lazy.hs view
@@ -0,0 +1,292 @@+{-# LANGUAGE BangPatterns, CPP #-}++------------------------------------------------------------------------+-- |+-- Module      :  Data.HashMap.Lazy+-- Copyright   :  2010-2011 Johan Tibell+-- License     :  BSD-style+-- Maintainer  :  johan.tibell@gmail.com+-- Stability   :  provisional+-- Portability :  portable+--+-- A map from /hashable/ keys to values.  A map cannot contain+-- duplicate keys; each key can map to at most one value.  A 'HashMap'+-- makes no guarantees as to the order of its elements.+--+-- This map is strict in the keys and lazy in the values; keys are+-- evaluated to /weak head normal form/ before they are added to the+-- map.+--+-- The implementation is based on /big-endian patricia trees/, keyed+-- by a hash of the original key.  A 'HashMap' is often faster than+-- other tree-based maps, especially when key comparison is expensive,+-- as in the case of strings.+--+-- Many operations have a worst-case complexity of /O(min(n,W))/.+-- This means that the operation can become linear in the number of+-- elements with a maximum of /W/ -- the number of bits in an 'Int'+-- (32 or 64).++module Data.HashMap.Lazy+    (+      HashMap++      -- * Construction+    , empty+    , singleton++      -- * Basic interface+    , null+    , size+    , lookup+    , insert+    , delete+    , insertWith++      -- * Transformations+    , map++      -- * Folds+    , foldl'+    , foldlWithKey'+    , foldr+    , foldrWithKey++      -- * Filter+    , filter+    , filterWithKey++      -- * Conversions+    , elems+    , keys++      -- ** Lists+    , toList+    , fromList+    ) where++import qualified Data.FullList.Lazy as FL+import Data.Hashable (Hashable(hash))+import qualified Data.List as List+import Prelude hiding (filter, foldr, lookup, map, null, pred)++#if defined(__GLASGOW_HASKELL__)+import GHC.Exts (build)+#endif++import Data.HashMap.Common++------------------------------------------------------------------------+-- * Basic interface++-- | /O(1)/ Return 'True' if this map is empty, 'False' otherwise.+null :: HashMap k v -> Bool+null Nil = True+null _   = False++-- | /O(n)/ Return the number of key-value mappings in this map.+size :: HashMap k v -> Int+size t = case t of+    Bin _ _ l r -> size l + size r+    Tip _ l     -> FL.size l+    Nil         -> 0++-- | /O(min(n,W))/ Return the value to which the specified key is+-- mapped, or 'Nothing' if this map contains no mapping for the key.+lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v+lookup k0 t = go h0 k0 t+  where+    h0 = hash k0+    go !h !k (Bin _ m l r)+      | zero h m  = go h k l+      | otherwise = go h k r+    go h k (Tip h' l)+      | h == h'   = FL.lookup k l+      | otherwise = Nothing+    go _ _ Nil    = Nothing+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE lookup #-}+#endif++-- | /O(1)/ Construct an empty map.+empty :: HashMap k v+empty = Nil++-- | /O(1)/ Construct a map with a single element.+singleton :: Hashable k => k -> v -> HashMap k v+singleton k v = Tip h $ FL.singleton k v+  where h = hash k+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE singleton #-}+#endif++-- | /O(min(n,W))/ Associate the specified value with the specified+-- key in this map.  If this map previously contained a mapping for+-- the key, the old value is replaced.+insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v+insert k0 v0 t0 = go h0 k0 v0 t0+  where+    h0 = hash k0+    go !h !k v t@(Bin p m l r)+        | nomatch h p m = join h (Tip h $ FL.singleton k v) p t+        | zero h m      = Bin p m (go h k v l) r+        | otherwise     = Bin p m l (go h k v r)+    go h k v t@(Tip h' l)+        | h == h'       = Tip h $ FL.insert k v l+        | otherwise     = join h (Tip h $ FL.singleton k v) h' t+    go h k v Nil        = Tip h $ FL.singleton k v+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insert #-}+#endif++-- | /O(min(n,W))/ Remove the mapping for the specified key from this+-- map if present.+delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v+delete k0 = go h0 k0+  where+    h0 = hash k0+    go !h !k t@(Bin p m l r)+        | nomatch h p m = t+        | zero h m      = bin p m (go h k l) r  -- takes this branch+        | otherwise     = bin p m l (go h k r)+    go h k t@(Tip h' l)+        | h == h'       = case FL.delete k l of+            Nothing -> Nil+            Just l' -> Tip h' l'+        | otherwise     = t+    go _ _ Nil          = Nil+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE delete #-}+#endif++-- | /O(min(n,W))/ Associate the value with the key in this map.  If+-- this map previously contained a mapping for the key, the old value+-- is replaced by the result of applying the given function to the new+-- and old value.  Example:+--+-- > insertWith f k v map+-- >   where f new old = new + old+insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v+           -> HashMap k v+insertWith f k0 v0 t0 = go h0 k0 v0 t0+  where+    h0 = hash k0+    go !h !k v t@(Bin p m l r)+        | nomatch h p m = join h (Tip h $ FL.singleton k v) p t+        | zero h m      = Bin p m (go h k v l) r+        | otherwise     = Bin p m l (go h k v r)+    go h k v t@(Tip h' l)+        | h == h'       = Tip h $ FL.insertWith f k v l+        | otherwise     = join h (Tip h $ FL.singleton k v) h' t+    go h k v Nil        = Tip h $ FL.singleton k v+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertWith #-}+#endif++------------------------------------------------------------------------+-- * Transformations++-- | /O(n)/ Transform this map by applying a function to every value.+map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2+map f = go+  where+    go (Bin p m l r) = Bin p m (go l) (go r)+    go (Tip h l)     = Tip h (FL.map f' l)+    go Nil           = Nil+    f' k v = (k, f v)+{-# INLINE map #-}++------------------------------------------------------------------------+-- * Folds++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldr :: (v -> a -> a) -> a -> HashMap k v -> a+foldr f = foldrWithKey (const f)+{-# INLINE foldr #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- right-identity of the operator).+foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a+foldrWithKey f = go+  where+    go z (Bin _ _ l r) = go (go z r) l+    go z (Tip _ l)     = FL.foldrWithKey f z l+    go z Nil           = z+{-# INLINE foldrWithKey #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldl' :: (a -> v -> a) -> a -> HashMap k v -> a+foldl' f = foldlWithKey' (\ z _ v -> f z v)+{-# INLINE foldl' #-}++-- | /O(n)/ Reduce this map by applying a binary operator to all+-- elements, using the given starting value (typically the+-- left-identity of the operator).  Each application of the operator+-- is evaluated before before using the result in the next+-- application.  This function is strict in the starting value.+foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a+foldlWithKey' f = go+  where+    go !z (Bin _ _ l r) = let z' = go z l+                          in z' `seq` go z' r+    go z (Tip _ l)      = FL.foldlWithKey' f z l+    go z Nil            = z+{-# INLINE foldlWithKey' #-}++------------------------------------------------------------------------+-- * Filter++-- | /O(n)/ Filter this map by retaining only elements satisfying a+-- predicate.+filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v+filterWithKey pred = go+  where+    go (Bin p m l r) = bin p m (go l) (go r)+    go (Tip h l)     = case FL.filterWithKey pred l of+        Just l' -> Tip h l'+        Nothing -> Nil+    go Nil           = Nil+{-# INLINE filterWithKey #-}++-- | /O(n)/ Filter this map by retaining only elements which values+-- satisfy a predicate.+filter :: (v -> Bool) -> HashMap k v -> HashMap k v+filter p = filterWithKey (\_ v -> p v)+{-# INLINE filter #-}++------------------------------------------------------------------------+-- Conversions++-- | /O(n)/ Return a list of this map's elements.  The list is+-- produced lazily.+toList :: HashMap k v -> [(k, v)]+#if defined(__GLASGOW_HASKELL__)+toList t = build (\ c z -> foldrWithKey (curry c) z t)+#else+toList = foldrWithKey (\ k v xs -> (k, v) : xs) []+#endif+{-# INLINE toList #-}++-- | /O(n*min(W, n))/ Construct a map from a list of elements.+fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v+fromList = List.foldl' (\ m (k, v) -> insert k v m) empty+{-# INLINE fromList #-}++-- | /O(n)/ Return a list of this map's keys.  The list is produced+-- lazily.+keys :: HashMap k v -> [k]+keys = List.map fst . toList+{-# INLINE keys #-}++-- | /O(n)/ Return a list of this map's values.  The list is produced+-- lazily.+elems :: HashMap k v -> [v]+elems = List.map snd . toList+{-# INLINE elems #-}
+ Data/HashMap/Strict.hs view
@@ -0,0 +1,148 @@+{-# LANGUAGE BangPatterns, CPP #-}++------------------------------------------------------------------------+-- |+-- Module      :  Data.HashMap.Strict+-- Copyright   :  2010-2011 Johan Tibell+-- License     :  BSD-style+-- Maintainer  :  johan.tibell@gmail.com+-- Stability   :  provisional+-- Portability :  portable+--+-- A map from /hashable/ keys to values.  A map cannot contain+-- duplicate keys; each key can map to at most one value.  A 'HashMap'+-- makes no guarantees as to the order of its elements.+--+-- This map is strict in both the keys and the values; keys and values+-- are evaluated to /weak head normal form/ before they are added to+-- the map.  Exception: the provided instances are the same as for the+-- lazy version of this module.+--+-- The implementation is based on /big-endian patricia trees/, keyed+-- by a hash of the original key.  A 'HashMap' is often faster than+-- other tree-based maps, especially when key comparison is expensive,+-- as in the case of strings.+--+-- Many operations have a worst-case complexity of /O(min(n,W))/.+-- This means that the operation can become linear in the number of+-- elements with a maximum of /W/ -- the number of bits in an 'Int'+-- (32 or 64).++module Data.HashMap.Strict+    (+      HashMap++      -- * Construction+    , empty+    , singleton++      -- * Basic interface+    , null+    , size+    , lookup+    , insert+    , delete+    , insertWith++      -- * Transformations+    , map++      -- * Folds+    , foldl'+    , foldlWithKey'+    , foldr+    , foldrWithKey++      -- * Filter+    , filter+    , filterWithKey++      -- * Conversions+    , elems+    , keys++      -- ** Lists+    , toList+    , fromList+    ) where++import Data.Hashable (Hashable(hash))+import Prelude hiding (filter, foldr, lookup, map, null)++import qualified Data.FullList.Strict as FL+import Data.HashMap.Common+import Data.HashMap.Lazy hiding (fromList, insert, insertWith, map, singleton)+import qualified Data.HashMap.Lazy as L+import qualified Data.List as List++------------------------------------------------------------------------+-- * Basic interface++-- | /O(1)/ Construct a map with a single element.+singleton :: Hashable k => k -> v -> HashMap k v+singleton k !v = L.singleton k v+{-# INLINE singleton #-}++-- | /O(min(n,W))/ Associate the specified value with the specified+-- key in this map.  If this map previously contained a mapping for+-- the key, the old value is replaced.+insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v+insert k0 !v0 t0 = go h0 k0 v0 t0+  where+    h0 = hash k0+    go !h !k v t@(Bin p m l r)+        | nomatch h p m = join h (Tip h $ FL.singleton k v) p t+        | zero h m      = Bin p m (go h k v l) r+        | otherwise     = Bin p m l (go h k v r)+    go h k v t@(Tip h' l)+        | h == h'       = Tip h $ FL.insert k v l+        | otherwise     = join h (Tip h $ FL.singleton k v) h' t+    go h k v Nil        = Tip h $ FL.singleton k v+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insert #-}+#endif++-- | /O(min(n,W))/ Associate the value with the key in this map.  If+-- this map previously contained a mapping for the key, the old value+-- is replaced by the result of applying the given function to the new+-- and old value.  Example:+--+-- > insertWith f k v map+-- >   where f new old = new + old+insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v+           -> HashMap k v+insertWith f k0 !v0 t0 = go h0 k0 v0 t0+  where+    h0 = hash k0+    go !h !k v t@(Bin p m l r)+        | nomatch h p m = join h (Tip h $ FL.singleton k v) p t+        | zero h m      = Bin p m (go h k v l) r+        | otherwise     = Bin p m l (go h k v r)+    go h k v t@(Tip h' l)+        | h == h'       = Tip h $ FL.insertWith f k v l+        | otherwise     = join h (Tip h $ FL.singleton k v) h' t+    go h k v Nil        = Tip h $ FL.singleton k v+#if __GLASGOW_HASKELL__ >= 700+{-# INLINABLE insertWith #-}+#endif++------------------------------------------------------------------------+-- * Transformations++-- | /O(n)/ Transform this map by applying a function to every value.+map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2+map f = go+  where+    go (Bin p m l r) = Bin p m (go l) (go r)+    go (Tip h l)     = Tip h (FL.map f' l)+    go Nil           = Nil+    f' k v = (k, f v)+{-# INLINE map #-}++------------------------------------------------------------------------+-- Conversions++-- | /O(n*min(W, n))/ Construct a map from a list of elements.+fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v+fromList = List.foldl' (\ m (k, v) -> insert k v m) empty+{-# INLINE fromList #-}
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c) 2010, Johan Tibell++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Johan Tibell nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ benchmarks/Benchmarks.hs view
@@ -0,0 +1,171 @@+{-# LANGUAGE GADTs #-}++module Main where++import Control.DeepSeq+import Control.Exception (evaluate)+import Control.Monad.Trans (liftIO)+import Criterion.Config+import Criterion.Main+import Data.Bits ((.&.))+import Data.Hashable (Hashable)+import qualified Data.ByteString as BS+import qualified Data.HashMap.Strict as HM+import qualified Data.IntMap as IM+import qualified Data.Map as M+import Data.List (foldl')+import Data.Maybe (fromMaybe)+import Prelude hiding (lookup)++import qualified Util.ByteString as UBS+import qualified Util.Int as UI+import qualified Util.String as US++instance NFData BS.ByteString++data B where+    B :: NFData a => a -> B++instance NFData B where+    rnf (B b) = rnf b++main :: IO ()+main = do+    let hm   = fromList elems :: HM.HashMap String Int+        hmbs = fromList elemsBS :: HM.HashMap BS.ByteString Int+        hmi  = fromList elemsI :: HM.HashMap Int Int+        m    = M.fromList elems :: M.Map String Int+        mbs  = M.fromList elemsBS :: M.Map BS.ByteString Int+        im   = IM.fromList elemsI :: IM.IntMap Int+    defaultMainWith defaultConfig+        (liftIO . evaluate $ rnf [B m, B mbs, B hm, B hmbs, B hmi, B im])+        [+          -- * Comparison to other data structures+          -- ** Map+          bgroup "Map"+          [ bgroup "lookup"+            [ bench "String" $ whnf (lookupM keys) m+            , bench "ByteString" $ whnf (lookupM keysBS) mbs+            ]+          , bgroup "insert"+            [ bench "String" $ whnf (insertM elems) M.empty+            , bench "ByteStringString" $ whnf (insertM elemsBS) M.empty+            ]+          , bgroup "delete"+            [ bench "String" $ whnf (insertM elems) M.empty+            , bench "ByteString" $ whnf (insertM elemsBS) M.empty+            ]+          ]++          -- ** IntMap+        , bgroup "IntMap"+          [ bench "lookup" $ whnf (lookupIM keysI) im+          , bench "insert" $ whnf (insertIM elemsI) IM.empty+          , bench "delete" $ whnf (deleteIM keysI) im+          ]++          -- * Basic interface+        , bgroup "lookup"+          [ bench "String" $ whnf (lookup keys) hm+          , bench "ByteString" $ whnf (lookup keysBS) hmbs+          , bench "Int" $ whnf (lookup keysI) hmi+          ]+        , bgroup "insert"+          [ bench "String" $ whnf (insert elems) HM.empty+          , bench "ByteString" $ whnf (insert elemsBS) HM.empty+          , bench "Int" $ whnf (insert elemsI) HM.empty+          ]+        , bgroup "delete"+          [ bench "String" $ whnf (delete keys) hm+          , bench "ByteString" $ whnf (delete keysBS) hmbs+          , bench "Int" $ whnf (delete keysI) hmi+          ]++          -- Transformations+        , bench "map" $ whnf (HM.map (\ v -> v + 1)) hmi++          -- Folds+        , bench "foldl'" $ whnf (HM.foldl' (+) 0) hmi+        , bench "foldr" $ whnf (HM.foldr (:) []) hmi++          -- Filter+        , bench "filter" $ whnf (HM.filter (\ v -> v .&. 1 == 0)) hmi+        , bench "filterWithKey" $ whnf (HM.filterWithKey (\ k _ -> k .&. 1 == 0)) hmi+        ]+  where+    n :: Int+    n = 2^(12 :: Int)++    elems   = zip keys [1..n]+    keys    = US.rnd 8 n+    elemsBS = zip keysBS [1..n]+    keysBS  = UBS.rnd 8 n+    elemsI  = zip keysI [1..n]+    keysI   = UI.rnd n n++------------------------------------------------------------------------+-- * HashMap++lookup :: (Eq k, Hashable k) => [k] -> HM.HashMap k Int -> Int+lookup xs m = foldl' (\z k -> fromMaybe z (HM.lookup k m)) 0 xs+{-# SPECIALIZE lookup :: [Int] -> HM.HashMap Int Int -> Int #-}+{-# SPECIALIZE lookup :: [String] -> HM.HashMap String Int -> Int #-}+{-# SPECIALIZE lookup :: [BS.ByteString] -> HM.HashMap BS.ByteString Int+                      -> Int #-}++insert :: (Eq k, Hashable k) => [(k, Int)] -> HM.HashMap k Int+       -> HM.HashMap k Int+insert xs m0 = foldl' (\m (k, v) -> HM.insert k v m) m0 xs+{-# SPECIALIZE insert :: [(Int, Int)] -> HM.HashMap Int Int+                      -> HM.HashMap Int Int #-}+{-# SPECIALIZE insert :: [(String, Int)] -> HM.HashMap String Int+                      -> HM.HashMap String Int #-}+{-# SPECIALIZE insert :: [(BS.ByteString, Int)] -> HM.HashMap BS.ByteString Int+                      -> HM.HashMap BS.ByteString Int #-}++delete :: (Eq k, Hashable k) => [k] -> HM.HashMap k Int -> HM.HashMap k Int+delete xs m0 = foldl' (\m k -> HM.delete k m) m0 xs+{-# SPECIALIZE delete :: [Int] -> HM.HashMap Int Int -> HM.HashMap Int Int #-}+{-# SPECIALIZE delete :: [String] -> HM.HashMap String Int+                      -> HM.HashMap String Int #-}+{-# SPECIALIZE delete :: [BS.ByteString] -> HM.HashMap BS.ByteString Int+                      -> HM.HashMap BS.ByteString Int #-}++------------------------------------------------------------------------+-- * Map++lookupM :: Ord k => [k] -> M.Map k Int -> Int+lookupM xs m = foldl' (\z k -> fromMaybe z (M.lookup k m)) 0 xs+{-# SPECIALIZE lookupM :: [String] -> M.Map String Int -> Int #-}+{-# SPECIALIZE lookupM :: [BS.ByteString] -> M.Map BS.ByteString Int -> Int #-}++insertM :: Ord k => [(k, Int)] -> M.Map k Int -> M.Map k Int+insertM xs m0 = foldl' (\m (k, v) -> M.insert k v m) m0 xs+{-# SPECIALIZE insertM :: [(String, Int)] -> M.Map String Int+                       -> M.Map String Int #-}+{-# SPECIALIZE insertM :: [(BS.ByteString, Int)] -> M.Map BS.ByteString Int+                       -> M.Map BS.ByteString Int #-}++deleteM :: Ord k => [k] -> M.Map k Int -> M.Map k Int+deleteM xs m0 = foldl' (\m k -> M.delete k m) m0 xs+{-# SPECIALIZE deleteM :: [String] -> M.Map String Int -> M.Map String Int #-}+{-# SPECIALIZE deleteM :: [BS.ByteString] -> M.Map BS.ByteString Int+                       -> M.Map BS.ByteString Int #-}++------------------------------------------------------------------------+-- * IntMap++lookupIM :: [Int] -> IM.IntMap Int -> Int+lookupIM xs m = foldl' (\z k -> fromMaybe z (IM.lookup k m)) 0 xs++insertIM :: [(Int, Int)] -> IM.IntMap Int -> IM.IntMap Int+insertIM xs m0 = foldl' (\m (k, v) -> IM.insert k v m) m0 xs++deleteIM :: [Int] -> IM.IntMap Int -> IM.IntMap Int+deleteIM xs m0 = foldl' (\m k -> IM.delete k m) m0 xs++------------------------------------------------------------------------+-- * Helpers++fromList :: (Eq k, Hashable k) => [(k, v)] -> HM.HashMap k v+fromList = foldl' (\m (k, v) -> HM.insert k v m) HM.empty
+ benchmarks/Makefile view
@@ -0,0 +1,42 @@+ghc-prof-flags :=+ifdef ENABLE_PROFILING+	ghc-prof-flags += -prof -hisuf p_hi -osuf p_o+	lib-suffix := _p+else+	lib-suffix :=+endif++ifdef GHC+	ghc:= $(GHC)+else+	ghc := ghc+endif++package := unordered-containers+version := $(shell awk '/^version:/{print $$2}' ../$(package).cabal)+lib := ../dist/build/libHS$(package)-$(version)$(lib-suffix).a+ghc-flags := -Wall -O2 -hide-all-packages \+	-package-conf ../dist/package.conf.inplace -package base -package mtl \+	-package unordered-containers -package containers -package criterion \+	-package deepseq -package hashable -package random -package bytestring \+	$(ghc-prof-flags) -rtsopts++%.o: %.hs+	$(ghc) $(ghc-flags) -c -o $@ $<++programs := bench++.PHONY: all+all: $(programs)++bench: $(lib) Benchmarks.o Util/Int.o Util/ByteString.o Util/String.o+	ranlib $(lib)+	$(ghc) $(ghc-flags) -threaded -o $@ $(filter %.o,$^) $(lib)++.PHONY: clean+clean:+	-find . \( -name '*.o' -o -name '*.hi' \) -exec rm {} \;+	-rm -f $(programs)++Benchmarks.o: Util/Int.o Util/ByteString.o Util/String.o+Util/ByteString.o: Util/String.o
+ benchmarks/Util/ByteString.hs view
@@ -0,0 +1,22 @@+-- | Benchmarking utilities.  For example, functions for generating+-- random 'ByteString's.+module Util.ByteString where++import qualified Data.ByteString as S+import qualified Data.ByteString.Char8 as C++import Util.String as String++-- | Generate a number of fixed length 'ByteString's where the content+-- of the strings are letters in ascending order.+asc :: Int  -- ^ Length of each string+    -> Int  -- ^ Number of strings+    -> [S.ByteString]+asc strlen num = map C.pack $ String.asc strlen num++-- | Generate a number of fixed length 'ByteString's where the content+-- of the strings are letters in random order.+rnd :: Int  -- ^ Length of each string+    -> Int  -- ^ Number of strings+    -> [S.ByteString]+rnd strlen num = map C.pack $ String.rnd strlen num
+ benchmarks/Util/Int.hs view
@@ -0,0 +1,12 @@+-- | Benchmarking utilities.  For example, functions for generating+-- random integers.+module Util.Int where++import System.Random (mkStdGen, randomRs)++-- | Generate a number of uniform random integers in the interval+-- @[0..upper]@.+rnd :: Int  -- ^ Upper bound (inclusive)+    -> Int  -- ^ Number of integers+    -> [Int]+rnd upper num = take num $ randomRs (0, upper) $ mkStdGen 1234
+ benchmarks/Util/String.hs view
@@ -0,0 +1,25 @@+-- | Benchmarking utilities.  For example, functions for generating+-- random strings.+module Util.String where++import System.Random (mkStdGen, randomRs)++-- | Generate a number of fixed length strings where the content of+-- the strings are letters in ascending order.+asc :: Int  -- ^ Length of each string+    -> Int  -- ^ Number of strings+    -> [String]+asc strlen num = take num $ iterate (snd . inc) $ replicate strlen 'a'+  where inc [] = (True, [])+        inc (c:cs) = case inc cs of (True, cs') | c == 'z'  -> (True, 'a' : cs')+                                                | otherwise -> (False, succ c : cs')+                                    (False, cs')            -> (False, c : cs')++-- | Generate a number of fixed length strings where the content of+-- the strings are letters in random order.+rnd :: Int  -- ^ Length of each string+    -> Int  -- ^ Number of strings+    -> [String]+rnd strlen num = take num $ split $ randomRs ('a', 'z') $ mkStdGen 1234+  where+    split cs = case splitAt strlen cs of (str, cs') -> str : split cs'
+ tests/Properties.hs view
@@ -0,0 +1,148 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}++-- | Tests for the 'Data.HashMap.Lazy' module.  We test functions by+-- comparing them to a simpler model, an association list.++module Main (main) where++import Data.Function (on)+import Data.Hashable (Hashable(hash))+import qualified Data.List as L+import qualified Data.HashMap.Lazy as M+import Test.QuickCheck (Arbitrary)+import Test.QuickCheck.Batch++-- Key type that generates more hash collisions.+newtype Key = K { unK :: Int }+            deriving (Arbitrary, Eq, Ord, Show)++instance Hashable Key where+    hash k = hash (unK k) `mod` 20++------------------------------------------------------------------------+-- * Properties++------------------------------------------------------------------------+-- ** Instances++pEq :: [(Key, Int)] -> [(Key, Int)] -> Bool+pEq xs = (xs ==) `eq` (fromList xs ==)++pNeq :: [(Key, Int)] -> [(Key, Int)] -> Bool+pNeq xs = (xs /=) `eq` (fromList xs /=)++------------------------------------------------------------------------+-- ** Basic interface++pSize :: [(Key, Int)] -> Bool+pSize = length `eq` M.size++pLookup :: Key -> [(Key, Int)] -> Bool+pLookup k = L.lookup k `eq` M.lookup k++pInsert :: Key -> Int -> [(Key, Int)] -> Bool+pInsert k v = insert (k, v) `eq` (toAscList . M.insert k v)++pDelete :: Key -> [(Key, Int)] -> Bool+pDelete k = delete k `eq` (toAscList . M.delete k)++pAdjustWithDefault :: Key -> [(Key, Int)] -> Bool+pAdjustWithDefault k = insertWith (+) (k, 1) `eq`+                       (toAscList . M.insertWith (+) k 1)++pToList :: [(Key, Int)] -> Bool+pToList = id `eq` toAscList++tests :: [TestOptions -> IO TestResult]+tests =+    [ run pEq+    , run pNeq+    , run pSize+    , run pLookup+    , run pInsert+    , run pDelete+    , run pAdjustWithDefault++      -- Folds+    , run pFoldr+    , run pFoldl'++      -- Conversions+    , run pToList+    ]++------------------------------------------------------------------------+-- ** Folds++pFoldr :: [(Int, Int)] -> Bool+pFoldr = (sortByKey . L.foldr (\ p z -> p : z) []) `eq`+         (sortByKey . M.foldrWithKey f [])+  where f k v z = (k, v) : z++pFoldl' :: Int -> [(Int, Int)] -> Bool+pFoldl' z0 = L.foldl' (\ z (_, v) -> z + v) z0 `eq` M.foldlWithKey' f z0+  where f _ v z = v + z++------------------------------------------------------------------------+-- Model++-- Invariant: the list is sorted in ascending order, by key.+type Model k v = [(k, v)]++-- | Check that a function operating on a 'HashMap' is equivalent to+-- one operating on a 'Model'.+eq :: (Eq a, Eq k, Hashable k, Ord k)+   => (Model k v -> a)      -- ^ Function that modifies a 'Model' in the same+                            -- way+   -> (M.HashMap k v -> a)  -- ^ Function that modified a 'HashMap'+   -> [(k, v)]              -- ^ Initial content of the 'HashMap' and 'Model'+   -> Bool                  -- ^ True if the functions are equivalent+eq f g xs = g (fromList ys) == f ys+  where ys = L.nubBy ((==) `on` fst) $ L.sortBy (compare `on` fst) $ xs++insert :: Ord k => (k, v) -> Model k v -> Model k v+insert x [] = [x]+insert x@(k, _) (y@(k', _):xs)+    | k == k'   = x : xs+    | k > k'    = y : insert x xs+    | otherwise = x : y : xs++delete :: Ord k => k -> Model k v -> Model k v+delete _ [] = []+delete k ys@(y@(k', _):xs)+    | k == k'   = xs+    | k > k'    = y : delete k xs+    | otherwise = ys++insertWith :: Ord k => (v -> v -> v) -> (k, v) -> Model k v -> Model k v+insertWith _ x [] = [x]+insertWith f x@(k, v) (y@(k', v'):xs)+    | k == k'   = (k', f v v') : xs+    | k > k'    = y : insertWith f x xs+    | otherwise = x : y : xs++------------------------------------------------------------------------+-- Test harness++options :: TestOptions+options = TestOptions+    { no_of_tests     = 500+    , length_of_tests = 1+    , debug_tests     = False+    }++main :: IO ()+main = runTests "basics" options tests++------------------------------------------------------------------------+-- Helpers++fromList :: (Eq k, Hashable k) => [(k, v)] -> M.HashMap k v+fromList = L.foldl' ins M.empty+  where ins m (k, v) = M.insert k v m++sortByKey :: Ord k => [(k, v)] -> [(k, v)]+sortByKey = L.sortBy (compare `on` fst)++toAscList :: Ord k => M.HashMap k v -> [(k, v)]+toAscList = sortByKey . M.toList
+ unordered-containers.cabal view
@@ -0,0 +1,63 @@+name:           unordered-containers+version:        0.1.0.0+synopsis:       Efficient hashing-based container types+description:+  Efficient hashing-based container types.  The containers have been+  optimized for performance critical use, both in terms of large data+  quantities and high speed.+  .+  The declared cost of each operation is either worst-case or+  amortized, but remains valid even if structures are shared.+license:        BSD3+license-file:   LICENSE+author:         Johan Tibell <johan.tibell@gmail.com>+maintainer:     johan.tibell@gmail.com+bug-reports:    https://github.com/tibbe/unordered-containers/issues+copyright:      (c) 2010-2011 Johan Tibell+category:       Data+build-type:     Simple+cabal-version:  >=1.8+-- The test files shouldn't have to go here, but the source files for+-- the test-suite stanzas don't get picked up by `cabal sdist`.+Extra-source-files:+  tests/Properties.hs, benchmarks/Benchmarks.hs benchmarks/Makefile+  benchmarks/Util/*.hs++library+  exposed-modules:+    Data.HashMap.Lazy+    Data.HashMap.Strict++  build-depends:+    base < 4.4,+    deepseq == 1.1.*,+    hashable >= 1.0.1.1 && < 1.2++  other-modules:+    Data.FullList.Lazy+    Data.FullList.Strict+    Data.HashMap.Common++  ghc-options: -Wall -O2+  if impl(ghc >= 6.8)+    ghc-options: -fwarn-tabs+  if impl(ghc > 6.10)+    ghc-options: -fregs-graph++-- -- Commented out until cabal-install release.+-- test-suite properties+--   hs-source-dirs: tests+--   main-is: Properties.hs+--   type: exitcode-stdio-1.0++--   build-depends:+--     base,+--     hashable >= 1.0.1.1 && < 1.1,+--     unordered-containers,+--     QuickCheck == 1.2.0.*++--   ghc-options: -Wall++source-repository head+  type:     git+  location: https://github.com/tibbe/unordered-containers.git