Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
Please see the documentation of containers for details.
- data Map k a :: * -> * -> *
- empty :: Map k a
- singleton :: k -> a -> Map k a
- fromSet :: (k -> a) -> Set k -> Map k a
- insert :: Ord k => k -> a -> Map k a -> Map k a
- delete :: Ord k => k -> Map k a -> Map k a
- lookup :: Ord k => k -> Map k a -> Maybe a
- member :: Ord k => k -> Map k a -> Bool
- null :: Map k a -> Bool
- union :: Ord k => Map k a -> Map k a -> Map k a
- difference :: Ord k => Map k a -> Map k b -> Map k a
- intersection :: Ord k => Map k a -> Map k b -> Map k a
- split :: Ord k => k -> Map k a -> (Map k a, Map k a)
Map type
A Map from keys k
to values a
.
Eq2 Map | Since: 0.5.9 |
Ord2 Map | Since: 0.5.9 |
Show2 Map | Since: 0.5.9 |
Functor (Map k) | |
Foldable (Map k) | |
Traversable (Map k) | |
Eq k => Eq1 (Map k) | Since: 0.5.9 |
Ord k => Ord1 (Map k) | Since: 0.5.9 |
(Ord k, Read k) => Read1 (Map k) | Since: 0.5.9 |
Show k => Show1 (Map k) | Since: 0.5.9 |
Ord k => IsList (Map k v) | Since: 0.5.6.2 |
(Eq k, Eq a) => Eq (Map k a) | |
(Data k, Data a, Ord k) => Data (Map k a) | |
(Ord k, Ord v) => Ord (Map k v) | |
(Ord k, Read k, Read e) => Read (Map k e) | |
(Show k, Show a) => Show (Map k a) | |
Ord k => Semigroup (Map k v) | |
Ord k => Monoid (Map k v) | |
(NFData k, NFData a) => NFData (Map k a) | |
type Item (Map k v) | |
Construction
singleton :: k -> a -> Map k a #
O(1). A map with a single element.
singleton 1 'a' == fromList [(1, 'a')] size (singleton 1 'a') == 1
fromSet :: (k -> a) -> Set k -> Map k a #
O(n). Build a map from a set of keys and a function which for each key computes its value.
fromSet (\k -> replicate k 'a') (Data.Set.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")] fromSet undefined Data.Set.empty == empty
Insertion
insert :: Ord k => k -> a -> Map k a -> Map k a #
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 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')] insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')] insert 5 'x' empty == singleton 5 'x'
Deletion/Update
delete :: Ord k => k -> Map k a -> Map k a #
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 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] delete 5 empty == empty
Query
Lookup
lookup :: Ord k => k -> Map k a -> Maybe a #
O(log n). Lookup the value at a key in the map.
The function will return the corresponding value as (
,
or Just
value)Nothing
if the key isn't in the map.
An example of using lookup
:
import Prelude hiding (lookup) import Data.Map employeeDept = fromList([("John","Sales"), ("Bob","IT")]) deptCountry = fromList([("IT","USA"), ("Sales","France")]) countryCurrency = fromList([("USA", "Dollar"), ("France", "Euro")]) employeeCurrency :: String -> Maybe String employeeCurrency name = do dept <- lookup name employeeDept country <- lookup dept deptCountry lookup country countryCurrency main = do putStrLn $ "John's currency: " ++ (show (employeeCurrency "John")) putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))
The output of this program:
John's currency: Just "Euro" Pete's currency: Nothing
member :: Ord k => k -> Map k a -> Bool #
O(log n). Is the key a member of the map? See also notMember
.
member 5 (fromList [(5,'a'), (3,'b')]) == True member 1 (fromList [(5,'a'), (3,'b')]) == False
Size
O(1). Is the map empty?
Data.Map.null (empty) == True Data.Map.null (singleton 1 'a') == False
Combine
Union
Difference
difference :: Ord k => Map k a -> Map k b -> Map k a #
O(m*log(n/m + 1)), m <= n. Difference of two maps. Return elements of the first map not existing in the second map.
difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
Intersection
intersection :: Ord k => Map k a -> Map k b -> Map k a #
O(m*log(n/m + 1)), m <= n. Intersection of two maps.
Return data in the first map for the keys existing in both maps.
(
).intersection
m1 m2 == intersectionWith
const
m1 m2
intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
Lists
Ordered lists
split :: Ord k => k -> Map k a -> (Map k a, Map k a) #
O(log n). The expression (
) is a pair split
k map(map1,map2)
where
the keys in map1
are smaller than k
and the keys in map2
larger than k
.
Any key equal to k
is found in neither map1
nor map2
.
split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")]) split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a") split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a") split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty) split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)