Map.dcl 6.63 KB
Newer Older
1
definition module Data.Map
2
/**
Camil Staps's avatar
Camil Staps committed
3 4 5 6
 * This module provides a dynamic Map type for creating mappings from keys to values
 * Internally it uses an AVL tree to organize the key-value pairs stored in the mapping
 * such that lookup, insert and delete operations can be performed in O(log n).
 */
7

8
from Data.Maybe		import :: Maybe (..)
9
from StdOverloaded	import class ==, class <
10 11
from StdBool        import not
from StdFunc        import id
12 13
from Text.JSON      import generic JSONEncode, generic JSONDecode, :: JSONNode
from GenEq import generic gEq
14
from Data.Monoid    import class Monoid, class Semigroup
15 16
import qualified StdList as SL
from Data.List import foldr
17
from Data.Functor import class Functor (..)
18
from StdOverloaded import class < (..)
19
import StdClass
20 21

/**
Camil Staps's avatar
Camil Staps committed
22 23 24 25 26 27 28 29
 * The abstract Map type provides the mapping.
 * For example "Map Int String" is a mapping "from" integers "to" strings.
 *
 * @var The key type on which the data structure is indexed.
 * @var The type of the values stored in the mapping.
 */
:: Map k v
  = Bin !Int !k !v !(Map k v) !(Map k v)
30 31 32
  | Tip

instance Monoid (Map k v) | < k
33

Camil Staps's avatar
Camil Staps committed
34
instance == (Map k v) | == k & == v
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
35

36 37
//Basic functions

Camil Staps's avatar
Camil Staps committed
38 39 40 41
/**
 * Check if a Map is empty.
 * @type (Map k a) -> Bool
 */
42 43 44
null mp :== case mp of
              Tip -> True
              _   -> False
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
45

46
/**
Camil Staps's avatar
Camil Staps committed
47 48 49
 * Create an empty Map.
 * @return An empty map
 */
50
newMap      :: w:(Map k u:v), [ w <= u]
51

Camil Staps's avatar
Camil Staps committed
52 53 54 55
/**
 * Create a Map with one element.
 */
singleton   :: !k !v -> Map k v
56

Camil Staps's avatar
Camil Staps committed
57 58 59
/**
 * The number of elements in a Map.
 */
60
mapSize     :: !(Map k v) -> Int
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
61

62
/**
Camil Staps's avatar
Camil Staps committed
63 64 65 66 67 68 69
 * Adds or replaces the value for a given key.
 *
 * @param The key value to add/update
 * @param The value to add/update at the key position
 * @param The original mapping
 * @return The modified mapping with the added value
 */
70
put :: !k !a !(Map k a) -> Map k a | < k
71

Camil Staps's avatar
Camil Staps committed
72 73 74 75 76 77 78 79 80
/**
 * Searches for a value at a given key position. Works only for non-unique
 * mappings.
 *
 * @type k (Map k v) -> Maybe v | < k
 * @param The key to look for
 * @param The orginal mapping
 * @return When found, the value at the key position, if not: Nothing
 */
81 82 83 84 85 86 87 88
get k m :== get` k m
  where
  get` _ Tip              = Nothing
  get` k (Bin _ kx x l r) = if (k < kx)
                              (get` k l)
                              (if (k > kx)
                                 (get` k r)
                                 (Just x))
89

Camil Staps's avatar
Camil Staps committed
90 91 92
/**
 * Searches for a value at a given key position. Works also for unique mappings.
 */
93
getU :: !k !w:(Map k v) -> x:(!Maybe v, !y:(Map k v)) | == k & < k, [ x <= y, w <= y]
Camil Staps's avatar
Camil Staps committed
94

95 96
/**
* Removes the value at a given key position. The mapping itself can be spine unique.
97 98 99 100 101
*
* @param The key to remove
* @param The original mapping
* @return The modified mapping with the value/key removed
*/
102
del :: !k !(Map k a) -> Map k a | < k
103

Camil Staps's avatar
Camil Staps committed
104 105 106
/**
 * Removes the value at a given key position. The mapping can be unique.
 */
107
delU :: !a !.(Map a b) -> u:(!v:(Maybe b), !Map a b) | == a & < a, [u <= v] // !k !w:(Map k u:v) -> x:(Maybe u:v, !y:(Map k u:v)) | == k & < k, [ w y <= u, x <= y, w <= y]
108

109 110
foldrWithKey :: !(k v u:a -> u:a) !u:a !(Map k v) -> u:a
foldlWithKey :: !(u:a k v -> u:a) !u:a !(Map k v) -> u:a
Camil Staps's avatar
Camil Staps committed
111 112 113 114 115 116 117 118 119 120

/**
 * @type (v a -> a) a (Map k v) -> a
 */
foldrNoKey f x m :== foldrWithKey (\_ v acc -> f v acc) x m

/**
 * @type (a v -> a) a (Map k v) -> a
 */
foldlNoKey f x m :== foldlWithKey (\acc _ v -> f acc v) x m
121

Camil Staps's avatar
Camil Staps committed
122 123 124 125 126 127 128 129
/**
 * Filter elements in a Map.
 *
 * @param The predicate function.
 * @param The Map.
 * @return A new Map that contains exactly those pairs (k,v) from the original Map for which p k v holds.
 */
filterWithKey :: !(k v -> Bool) !(Map k v) -> Map k v
130

Camil Staps's avatar
Camil Staps committed
131 132 133 134
/**
 * A list of the keys in a Map.
 * @type (Map k v) -> [k]
 */
135
keys m :== foldrWithKey (\k _ ks -> [k : ks]) [] m
Camil Staps's avatar
Camil Staps committed
136 137 138 139 140

/**
 * A list of the elements in a Map.
 * @type (Map k v) -> [v]
 */
141
elems m :== foldrNoKey (\x xs -> [x:xs]) [] m
142

143 144 145
//Conversion functions

/**
Camil Staps's avatar
Camil Staps committed
146 147 148 149 150 151 152 153
 * Converts a mapping to a list of key value pairs.
 * Because of the internal ordering of the mapping the resulting
 * list is sorted ascending on the key part of the tuple.
 *
 * @type (Map k v) -> [(k,v)]
 * @param The original mapping
 * @return A list of key/value tuples in the mapping
 */
154
toList m :== toAscList m
155 156

/**
Camil Staps's avatar
Camil Staps committed
157 158 159 160
 * Same as toList.
 * @type (Map k v) -> [(k,v)]
 */
toAscList m :== foldrWithKey (\k x xs -> [(k,x):xs]) [] m
161 162

/**
Camil Staps's avatar
Camil Staps committed
163 164 165 166 167 168
 * Converts a list of key/value tuples to a mapping.
 *
 * @param A list of key/value tuples
 * @return A mapping containing all the tuples in the list
 */
fromList :: !u:[v:(!a, !b)] -> Map a b | == a & < a, [u <= v]
169 170 171 172

derive JSONEncode Map
derive JSONDecode Map
derive gEq Map
173

Camil Staps's avatar
Camil Staps committed
174 175 176
/**
 * Check if a key exists in a Map.
 */
177
member :: !k !(Map k a) -> Bool | < k
178

Camil Staps's avatar
Camil Staps committed
179 180 181 182
/**
 * Checks if a key is not a member of a Map.
 * @type k (Map k v) -> Bool | < k
 */
183 184
notMember k m :== not (member k m)

Camil Staps's avatar
Camil Staps committed
185 186 187 188
/**
 * Find an element in a Map.
 * Aborts when the element is not found.
 */
189
find :: !k !(Map k a) -> a | < k
190

Camil Staps's avatar
Camil Staps committed
191 192 193 194 195 196 197
/**
 * Find an element in a Map.
 * When the key does not exist, return a default.
 *
 * @param The default.
 * @param The key to look up.
 */
198
findWithDefault :: !a !k !(Map k a) -> a | < k
199

200
alter :: !((Maybe a) -> Maybe a) !k !(Map k a) -> Map k a | < k
201

202
elemAt :: !Int !(Map k a) -> (!k, !a)
203

204
findMin :: !(Map k a) -> (!k, !a)
205

206
findMax :: !(Map k a) -> (!k, !a)
207

208
unions :: ![Map k a] -> Map k a | < k
209

210
unionsWith :: !(a a -> a) ![Map k a] -> Map k a | < k
211

212
unionWith :: !(a a -> a) !(Map k a) !(Map k a) -> Map k a | < k
213

214
unionWithKey :: !(k a a -> a) !(Map k a) !(Map k a) -> Map k a | < k
215

216 217 218 219 220 221
intersection :: !(Map k a) !(Map k b) -> Map k a | < k

intersectionWith :: !(a b -> c) !(Map k a) !(Map k b) -> Map k c | < k

intersectionWithKey :: !(k a b -> c) !(Map k a) !(Map k b) -> Map k c | < k

222
union :: !(Map k a) !(Map k a) -> Map k a | < k
223 224 225 226 227 228

mergeWithKey :: !(k a b -> Maybe c) !((Map k a) -> Map k c) !((Map k b) -> Map k c)
             !(Map k a) !(Map k b) -> Map k c | < k

foldlStrict :: !(a b -> a) !a ![b] -> a

Camil Staps's avatar
Camil Staps committed
229 230 231 232 233 234 235 236
/**
 * Removes the values at given key positions. The mapping itself can be spine unique.
 *
 * @type [a] (Map a b) -> Map a b | <, == a
 * @param The list of keys to remove
 * @param The original mapping
 * @return The modified mapping with the values/keys removed
 */
237 238
delList xs m :== 'SL'.foldr (\k m -> del k m) m xs

Camil Staps's avatar
Camil Staps committed
239 240 241 242 243 244 245 246
/**
 * Adds or replaces a list of key/value pairs.
 *
 * @type [(a, b)] (Map a b) -> Map a b | ==, < a
 * @param A list of key/value tuples
 * @param The original mapping
 * @return The modified mapping with the added values
 */
247 248
putList xs m :== union (fromList xs) m

249
instance Functor (Map k)
250 251

difference :: !(Map k a) !(Map k b) -> Map k a | < k
252 253 254
mapWithKey :: !(k a -> b) !(Map k a) -> Map k b
isSubmapOf :: !(Map k a) !(Map k a) -> Bool | < k & Eq a
isSubmapOfBy :: !(a b -> Bool) !(Map k a) !(Map k b) -> Bool | < k