1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
{-# LANGUAGE Safe #-}
------------------------------------------------------------------------
-- |
-- Module : Data.HashMap.Strict
-- Copyright : 2010-2012 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.
--
-- The implementation is based on /hash array mapped tries/. A
-- 'HashMap' is often faster than other tree-based set types,
-- especially when key comparison is expensive, as in the case of
-- strings.
--
-- Many operations have a average-case complexity of \(O(\log n)\). The
-- implementation uses a large base (i.e. 16) so in practice these
-- operations are constant time.
module Data.HashMap.Strict
(
-- * Strictness properties
-- $strictness
HashMap
-- * Construction
, empty
, singleton
-- * Basic interface
, null
, size
, member
, lookup
, (!?)
, findWithDefault
, lookupDefault
, (!)
, insert
, insertWith
, delete
, adjust
, update
, alter
, alterF
, isSubmapOf
, isSubmapOfBy
-- * Combine
-- ** Union
, union
, unionWith
, unionWithKey
, unions
-- ** Compose
, compose
-- * Transformations
, map
, mapWithKey
, traverseWithKey
, mapKeys
-- * Difference and intersection
, difference
, differenceWith
, intersection
, intersectionWith
, intersectionWithKey
-- * Folds
, foldMapWithKey
, foldr
, foldl
, foldr'
, foldl'
, foldrWithKey'
, foldlWithKey'
, foldrWithKey
, foldlWithKey
-- * Filter
, filter
, filterWithKey
, mapMaybe
, mapMaybeWithKey
-- * Conversions
, keys
, elems
-- ** Lists
, toList
, fromList
, fromListWith
, fromListWithKey
-- ** HashSets
, HS.keysSet
) where
import Data.HashMap.Internal.Strict
import Prelude ()
import qualified Data.HashSet.Internal as HS
-- $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.
|
