Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

## Synopsis

- (!) :: Ord k => Map k a -> k -> a
- elemAt :: Int -> Map k a -> (k, a)
- deleteAt :: Int -> Map k a -> Map k a
- findIndex :: Ord k => k -> Map k a -> Int
- updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
- findMin :: Map k a -> (k, a)
- findMax :: Map k a -> (k, a)
- deleteFindMin :: Map k a -> ((k, a), Map k a)
- deleteFindMax :: Map k a -> ((k, a), Map k a)

# Operators

(!) :: Ord k => Map k a -> k -> a infixl 9 #

*O(log n)*. Find the value at a key.
Calls `error`

when the element can not be found.

fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map fromList [(5,'a'), (3,'b')] ! 5 == 'a'

# Indexed

elemAt :: Int -> Map k a -> (k, a) #

*O(log n)*. Retrieve an element by its *index*, i.e. by its zero-based
index in the sequence sorted by keys. If the *index* is out of range (less
than zero, greater or equal to `size`

of the map), `error`

is called.

elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b") elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a") elemAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range

deleteAt :: Int -> Map k a -> Map k a #

*O(log n)*. Delete the element at *index*, i.e. by its zero-based index in
the sequence sorted by keys. If the *index* is out of range (less than zero,
greater or equal to `size`

of the map), `error`

is called.

deleteAt 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" deleteAt 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" deleteAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range deleteAt (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range

findIndex :: Ord k => k -> Map k a -> Int #

*O(log n)*. Return the *index* of a key, which is its zero-based index in
the sequence sorted by keys. The index is a number from *0* up to, but not
including, the `size`

of the map. Calls `error`

when the key is not
a `member`

of the map.

findIndex 2 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0 findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1 findIndex 6 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map

updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a #

*O(log n)*. Update the element at *index*. Calls `error`

when an
invalid index is used.

updateAt (\ _ _ -> Just "x") 0 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")] updateAt (\ _ _ -> Just "x") 1 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")] updateAt (\ _ _ -> Just "x") 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" updateAt (\_ _ -> Nothing) 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" updateAt (\_ _ -> Nothing) 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range updateAt (\_ _ -> Nothing) (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range

# Min/Max

findMin :: Map k a -> (k, a) #

*O(log n)*. The minimal key of the map. Calls `error`

if the map is empty.

findMin (fromList [(5,"a"), (3,"b")]) == (3,"b") findMin empty Error: empty map has no minimal element

deleteFindMin :: Map k a -> ((k, a), Map k a) #

*O(log n)*. Delete and find the minimal element.

deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) deleteFindMin Error: can not return the minimal element of an empty map

deleteFindMax :: Map k a -> ((k, a), Map k a) #

*O(log n)*. Delete and find the maximal element.

deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) deleteFindMax empty Error: can not return the maximal element of an empty map