content: {-# LANGUAGE Haskell98 #-}
  {-# LINE 1 "Data/Map/Lazy.hs" #-}
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  {-# LANGUAGE CPP #-}
  {-# LANGUAGE Safe #-}
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  -----------------------------------------------------------------------------
  -- |
  -- Module      :  Data.Map.Lazy
  -- Copyright   :  (c) Daan Leijen 2002
  --                (c) Andriy Palamarchuk 2008
  -- License     :  BSD-style
  -- Maintainer  :  libraries@haskell.org
  -- Stability   :  provisional
  -- Portability :  portable
  --
  -- An efficient implementation of ordered maps from keys to values
  -- (dictionaries).
  --
  -- API of this module is strict in the keys, but lazy in the values.
  -- If you need value-strict maps, use "Data.Map.Strict" instead.
  -- The 'Map' type itself is shared between the lazy and strict modules,
  -- meaning that the same 'Map' value can be passed to functions in
  -- both modules (although that is rarely needed).
  --
  -- These modules are intended to be imported qualified, to avoid name
  -- clashes with Prelude functions, e.g.
  --
  -- >  import qualified Data.Map.Lazy as Map
  --
  -- The implementation of 'Map' is based on /size balanced/ binary trees (or
  -- trees of /bounded balance/) as described by:
  --
  --    * Stephen Adams, \"/Efficient sets: a balancing act/\",
  --     Journal of Functional Programming 3(4):553-562, October 1993,
  --     <http://www.swiss.ai.mit.edu/~adams/BB/>.
  --
  --    * J. Nievergelt and E.M. Reingold,
  --      \"/Binary search trees of bounded balance/\",
  --      SIAM journal of computing 2(1), March 1973.
  --
  -- 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'.
  --
  -- /Warning/: The size of the map must not exceed @maxBound::Int@. Violation of
  -- this condition is not detected and if the size limit is exceeded, its
  -- behaviour is undefined.
  --
  -- Operation comments contain the operation time complexity in
  -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
  -----------------------------------------------------------------------------
  
  module Data.Map.Lazy (
      -- * Strictness properties
      -- $strictness
  
      -- * Map type
      Map              -- instance Eq,Show,Read
  
      -- * Operators
      , (!), (\\)
  
      -- * Query
      , M.null
      , size
      , member
      , notMember
      , M.lookup
      , findWithDefault
      , lookupLT
      , lookupGT
      , lookupLE
      , lookupGE
  
      -- * Construction
      , empty
      , singleton
  
      -- ** Insertion
      , insert
      , insertWith
      , insertWithKey
      , insertLookupWithKey
  
      -- ** Delete\/Update
      , delete
      , adjust
      , adjustWithKey
      , update
      , updateWithKey
      , updateLookupWithKey
      , alter
  
      -- * Combine
  
      -- ** Union
      , union
      , unionWith
      , unionWithKey
      , unions
      , unionsWith
  
      -- ** Difference
      , difference
      , differenceWith
      , differenceWithKey
  
      -- ** Intersection
      , intersection
      , intersectionWith
      , intersectionWithKey
  
      -- ** Universal combining function
      , mergeWithKey
  
      -- * Traversal
      -- ** Map
      , M.map
      , mapWithKey
      , traverseWithKey
      , mapAccum
      , mapAccumWithKey
      , mapAccumRWithKey
      , mapKeys
      , mapKeysWith
      , mapKeysMonotonic
  
      -- * Folds
      , M.foldr
      , M.foldl
      , foldrWithKey
      , foldlWithKey
      , foldMapWithKey
  
      -- ** Strict folds
      , foldr'
      , foldl'
      , foldrWithKey'
      , foldlWithKey'
  
      -- * Conversion
      , elems
      , keys
      , assocs
      , keysSet
      , fromSet
  
      -- ** Lists
      , toList
      , fromList
      , fromListWith
      , fromListWithKey
  
      -- ** Ordered lists
      , toAscList
      , toDescList
      , fromAscList
      , fromAscListWith
      , fromAscListWithKey
      , fromDistinctAscList
  
      -- * Filter
      , M.filter
      , filterWithKey
      , partition
      , partitionWithKey
  
      , mapMaybe
      , mapMaybeWithKey
      , mapEither
      , mapEitherWithKey
  
      , split
      , splitLookup
      , splitRoot
  
      -- * Submap
      , isSubmapOf, isSubmapOfBy
      , isProperSubmapOf, isProperSubmapOfBy
  
      -- * Indexed
      , lookupIndex
      , findIndex
      , elemAt
      , updateAt
      , deleteAt
  
      -- * Min\/Max
      , findMin
      , findMax
      , deleteMin
      , deleteMax
      , deleteFindMin
      , deleteFindMax
      , updateMin
      , updateMax
      , updateMinWithKey
      , updateMaxWithKey
      , minView
      , maxView
      , minViewWithKey
      , maxViewWithKey
  
      -- * Debugging
      , showTree
      , showTreeWith
      , valid
  
  
      ) where
  
  import Data.Map.Base as M
  
  -- $strictness
  --
  -- This module satisfies the following strictness property:
  --
  -- * Key arguments are evaluated to WHNF
  --
  -- Here are some examples that illustrate the property:
  --
  -- > insertWith (\ new old -> old) undefined v m  ==  undefined
  -- > insertWith (\ new old -> old) k undefined m  ==  OK
  -- > delete undefined m  ==  undefined
  