Dict

A dictionary mapping unique keys to values. The keys can be any comparable type. This includes Int, Float, Time, Char, String, and tuples or lists of comparable types.

Insert, remove, and query operations all take O(log n) time.

type Dict k v
A dictionary of keys and values. So a (Dict String User) is a dictionary that lets you look up a String (such as user names) and find the associated User.

empty : Dict k v
Create an empty dictionary.

singleton : comparable -> v -> Dict comparable v
Create a dictionary with one key-value pair.

insert : comparable -> v -> Dict comparable v -> Dict comparable v
Insert a key-value pair into a dictionary. Replaces value when there is a collision.

update : comparable -> (Maybe v -> Maybe v) -> Dict comparable v -> Dict comparable v
Update the value of a dictionary for a specific key with a given function.

remove : comparable -> Dict comparable v -> Dict comparable v
Remove a key-value pair from a dictionary. If the key is not found, no changes are made.

isEmpty : Dict k v -> Bool
Determine if a dictionary is empty.

member : comparable -> Dict comparable v -> Bool
Determine if a key is in a dictionary.

get : comparable -> Dict comparable v -> Maybe v
Get the value associated with a key. If the key is not found, return Nothing. This is useful when you are not sure if a key will be in the dictionary.

animals = fromList [ ("Tom", Cat), ("Jerry", Mouse) ]

get "Tom"   animals == Just Cat
get "Jerry" animals == Just Mouse
get "Spike" animals == Nothing

size : Dict k v -> Int
Determine the number of key-value pairs in the dictionary.

keys : Dict comparable v -> List comparable
Get all of the keys in a dictionary, sorted from lowest to highest.

keys (fromList [(0,"Alice"),(1,"Bob")]) == [0,1]

values : Dict comparable v -> List v
Get all of the values in a dictionary, in the order of their keys.

values (fromList [(0,"Alice"),(1,"Bob")]) == ["Alice", "Bob"]

toList : Dict comparable v -> List (comparable, v)
Convert a dictionary into an association list of key-value pairs, sorted by keys.

fromList : List (comparable, v) -> Dict comparable v
Convert an association list into a dictionary.

map : (comparable -> a -> b) -> Dict comparable a -> Dict comparable b
Apply a function to all values in a dictionary.

foldl : (comparable -> v -> b -> b) -> b -> Dict comparable v -> b
Fold over the key-value pairs in a dictionary, in order from lowest key to highest key.

foldr : (comparable -> v -> b -> b) -> b -> Dict comparable v -> b
Fold over the key-value pairs in a dictionary, in order from highest key to lowest key.

filter : (comparable -> v -> Bool) -> Dict comparable v -> Dict comparable v
Keep a key-value pair when it satisfies a predicate.

partition : (comparable -> v -> Bool) -> Dict comparable v -> (Dict comparable v, Dict comparable v)
Partition a dictionary according to a predicate. The first dictionary contains all key-value pairs which satisfy the predicate, and the second contains the rest.

union : Dict comparable v -> Dict comparable v -> Dict comparable v
Combine two dictionaries. If there is a collision, preference is given to the first dictionary.

intersect : Dict comparable v -> Dict comparable v -> Dict comparable v
Keep a key-value pair when its key appears in the second dictionary. Preference is given to values in the first dictionary.

diff : Dict comparable v -> Dict comparable v -> Dict comparable v
Keep a key-value pair when its key does not appear in the second dictionary.

merge :
  (comparable -> a -> r -> r) ->
  (comparable -> a -> b -> r -> r) ->
  (comparable -> b -> r -> r) ->
  Dict comparable a ->
  Dict comparable b ->
  r ->
  r

The most general way of combining two dictionaries. You provide three accumulators for when a given key appears:

  • Only in the left dictionary.
  • In both dictionaries.
  • Only in the right dictionary.

    You then traverse all the keys from lowest to highest, building up whatever you want.