{-# LANGUAGE CPP #-} {-# LANGUAGE BangPatterns #-} #if __GLASGOW_HASKELL__ >= 703 {-# LANGUAGE Safe #-} #endif #include "containers.h" ----------------------------------------------------------------------------- -- | -- Module : Data.Map.Strict -- Copyright : (c) Daan Leijen 2002 -- (c) Andriy Palamarchuk 2008 -- License : BSD-style -- Maintainer : [email protected] -- Portability : portable -- -- An efficient implementation of ordered maps from keys to values -- (dictionaries). -- -- API of this module is strict in both the keys and the values. -- If you need value-lazy maps, use "Data.Map.Lazy" instead. -- The 'Map' type 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.Strict 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. -- -- Bounds for 'union', 'intersection', and 'difference' are as given -- by -- -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun, -- \"/Just Join for Parallel Ordered Sets/\", -- <https://arxiv.org/abs/1602.02120v3>. -- -- 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>). -- -- Be aware that the 'Functor', 'Traversable' and 'Data' instances -- are the same as for the "Data.Map.Lazy" module, so if they are used -- on strict maps, the resulting maps will be lazy. ----------------------------------------------------------------------------- -- See the notes at the beginning of Data.Map.Internal. module Data.Map.Strict ( -- * Strictness properties -- $strictness -- * Map type Map -- instance Eq,Show,Read -- * Operators , (!), (!?), (\\) -- * Query , null , size , member , notMember , lookup , findWithDefault , lookupLT , lookupGT , lookupLE , lookupGE -- * Construction , empty , singleton -- ** Insertion , insert , insertWith , insertWithKey , insertLookupWithKey -- ** Delete\/Update , delete , adjust , adjustWithKey , update , updateWithKey , updateLookupWithKey , alter , alterF -- * Combine -- ** Union , union , unionWith , unionWithKey , unions , unionsWith -- ** Difference , difference , differenceWith , differenceWithKey -- ** Intersection , intersection , intersectionWith , intersectionWithKey -- ** General combining functions -- | See "Data.Map.Merge.Strict" -- ** Deprecated general combining function , mergeWithKey -- * Traversal -- ** Map , map , mapWithKey , traverseWithKey , traverseMaybeWithKey , mapAccum , mapAccumWithKey , mapAccumRWithKey , mapKeys , mapKeysWith , mapKeysMonotonic -- * Folds , foldr , 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 , fromDescList , fromDescListWith , fromDescListWithKey , fromDistinctDescList -- * Filter , filter , filterWithKey , restrictKeys , withoutKeys , partition , partitionWithKey , takeWhileAntitone , dropWhileAntitone , spanAntitone , mapMaybe , mapMaybeWithKey , mapEither , mapEitherWithKey , split , splitLookup , splitRoot -- * Submap , isSubmapOf, isSubmapOfBy , isProperSubmapOf, isProperSubmapOfBy -- * Indexed , lookupIndex , findIndex , elemAt , updateAt , deleteAt , take , drop , splitAt -- * Min\/Max , lookupMin , lookupMax , findMin , findMax , deleteMin , deleteMax , deleteFindMin , deleteFindMax , updateMin , updateMax , updateMinWithKey , updateMaxWithKey , minView , maxView , minViewWithKey , maxViewWithKey -- * Debugging , showTree , showTreeWith , valid ) where import Data.Map.Strict.Internal import Prelude () -- $strictness -- -- This module satisfies the following strictness properties: -- -- 1. Key arguments are evaluated to WHNF; -- -- 2. Keys and values are evaluated to WHNF before they are stored in -- the map. -- -- Here's an example illustrating the first property: -- -- > delete undefined m == undefined -- -- Here are some examples that illustrate the second property: -- -- > map (\ v -> undefined) m == undefined -- m is not empty -- > mapKeys (\ k -> undefined) m == undefined -- m is not empty