This is an alternative site for discovering Elm packages.
You may be looking for the
official Elm package site
instead.

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.

type alias Dict comparable v =
Tree comparable 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 comparable 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.

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
```

isEmpty : Dict comparable v -> Bool

Determine if a dictionary is empty.

```
isEmpty empty == True
```

member : comparable -> Dict comparable v -> Bool

Determine if a key is in a dictionary.

size : Dict comparable v -> Int

Determine the number of key-value pairs in the dictionary.

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 -> result -> result)
-> (comparable -> a -> b -> result -> result)
-> (comparable -> b -> result -> result)
-> Dict comparable a
-> Dict comparable b
-> result
-> result

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.

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.

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"]
```

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.

```
module CollectionsNg.Dict
exposing
( Dict
, empty
, singleton
, isEmpty
, size
, get
, member
, insert
, update
, remove
, fromList
, toList
, keys
, values
, map
, foldl
, foldr
, filter
, partition
, union
, intersect
, diff
, merge
)
{-| 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.
# Dictionary
@docs Dict
# Build
@docs empty, singleton, insert, update, remove
# Query
@docs get, isEmpty, member, size
# Combine
@docs union, intersect, diff, merge
# Lists
@docs toList, fromList, keys, values
# Transform
@docs map, foldl, foldr, filter, partition
-}
import CollectionsNg.Hamt as Hamt exposing (Tree)
import Murmur3
{-| 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`.
-}
type alias Dict comparable v =
Tree comparable v
hashFn : a -> Int
hashFn obj =
Murmur3.hashString 19456 <| toString obj
{-| Create an empty dictionary.
-}
empty : Dict comparable v
empty =
Hamt.empty
{-| Create a dictionary with one key-value pair.
-}
singleton : comparable -> v -> Dict comparable v
singleton key val =
insert key val empty
{-| Determine if a dictionary is empty.
isEmpty empty == True
-}
isEmpty : Dict comparable v -> Bool
isEmpty dict =
dict == Hamt.empty
{-| Determine the number of key-value pairs in the dictionary.
-}
size : Dict comparable v -> Int
size =
Hamt.size
{-| 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
-}
get : comparable -> Dict comparable v -> Maybe v
get key dict =
Hamt.get (hashFn key) key dict
{-| Determine if a key is in a dictionary.
-}
member : comparable -> Dict comparable v -> Bool
member key dict =
case get key dict of
Just _ ->
True
Nothing ->
False
{-| Insert a key-value pair into a dictionary. Replaces value when there is
a collision.
-}
insert : comparable -> v -> Dict comparable v -> Dict comparable v
insert key value dict =
Hamt.set (hashFn key) key value dict
{-| Update the value of a dictionary for a specific key with a given function.
-}
update : comparable -> (Maybe v -> Maybe v) -> Dict comparable v -> Dict comparable v
update key fn dict =
case fn <| get key dict of
Just val ->
insert key val dict
Nothing ->
remove key dict
{-| Remove a key-value pair from a dictionary. If the key is not found,
no changes are made.
-}
remove : comparable -> Dict comparable v -> Dict comparable v
remove key dict =
Hamt.remove (hashFn key) key dict
-- LISTS
{-| Convert an association list into a dictionary.
-}
fromList : List ( comparable, v ) -> Dict comparable v
fromList list =
List.foldl (\( key, value ) acc -> insert key value acc) empty list
{-| Convert a dictionary into an association list of key-value pairs, sorted by keys.
-}
toList : Dict comparable v -> List ( comparable, v )
toList dict =
foldl (\k v acc -> ( k, v ) :: acc) [] dict
{-| Get all of the keys in a dictionary, sorted from lowest to highest.
keys (fromList [(0,"Alice"),(1,"Bob")]) == [0,1]
-}
keys : Dict comparable v -> List comparable
keys dict =
foldl (\k _ acc -> k :: acc) [] dict
{-| Get all of the values in a dictionary, in the order of their keys.
values (fromList [(0,"Alice"),(1,"Bob")]) == ["Alice", "Bob"]
-}
values : Dict comparable v -> List v
values dict =
foldl (\_ v acc -> v :: acc) [] dict
-- TRANSFORM
{-| Apply a function to all values in a dictionary.
-}
map : (comparable -> a -> b) -> Dict comparable a -> Dict comparable b
map f dict =
Hamt.foldl (\key val acc -> insert key (f key val) acc) empty dict
{-| Fold over the key-value pairs in a dictionary, in order from lowest
key to highest key.
-}
foldl : (comparable -> v -> b -> b) -> b -> Dict comparable v -> b
foldl f acc dict =
Hamt.foldl f acc dict
{-| Fold over the key-value pairs in a dictionary, in order from highest
key to lowest key.
-}
foldr : (comparable -> v -> b -> b) -> b -> Dict comparable v -> b
foldr f acc t =
Hamt.foldl f acc t
{-| Keep a key-value pair when it satisfies a predicate.
-}
filter : (comparable -> v -> Bool) -> Dict comparable v -> Dict comparable v
filter predicate dictionary =
let
add key value dict =
if predicate key value then
insert key value dict
else
dict
in
foldl add empty dictionary
{-| 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.
-}
partition : (comparable -> v -> Bool) -> Dict comparable v -> ( Dict comparable v, Dict comparable v )
partition predicate dict =
let
add key value ( t1, t2 ) =
if predicate key value then
( insert key value t1, t2 )
else
( t1, insert key value t2 )
in
foldl add ( empty, empty ) dict
-- COMBINE
{-| Combine two dictionaries. If there is a collision, preference is given
to the first dictionary.
-}
union : Dict comparable v -> Dict comparable v -> Dict comparable v
union t1 t2 =
foldl insert t2 t1
{-| Keep a key-value pair when its key appears in the second Dictionary.
Preference is given to values in the first Dictionary.
-}
intersect : Dict comparable v -> Dict comparable v -> Dict comparable v
intersect t1 t2 =
filter (\k _ -> member k t2) t1
{-| Keep a key-value pair when its key does not appear in the second Dictionary.
-}
diff : Dict comparable v -> Dict comparable v -> Dict comparable v
diff t1 t2 =
foldl (\k v t -> remove k t) t1 t2
{-| The most general way of combining two dictionaries. You provide three
accumulators for when a given key appears:
1. Only in the left dictionary.
2. In both dictionaries.
3. Only in the right dictionary.
You then traverse all the keys from lowest to highest, building up whatever
you want.
-}
merge :
(comparable -> a -> result -> result)
-> (comparable -> a -> b -> result -> result)
-> (comparable -> b -> result -> result)
-> Dict comparable a
-> Dict comparable b
-> result
-> result
merge leftStep bothStep rightStep leftDict rightDict initialResult =
let
stepState ( rKey, rValue ) ( list, result ) =
case list of
[] ->
( list, rightStep rKey rValue result )
( lKey, lValue ) :: rest ->
if lKey < rKey then
stepState ( rKey, rValue ) ( rest, leftStep lKey lValue result )
else if lKey > rKey then
( list, rightStep rKey rValue result )
else
( rest, bothStep lKey lValue rValue result )
leftSortedPairs =
leftDict
|> toList
|> List.sortBy fst
rightSortedPairs =
rightDict
|> toList
|> List.sortBy fst
( leftovers, intermediateResult ) =
List.foldl stepState ( leftSortedPairs, initialResult ) rightSortedPairs
in
List.foldl (\( k, v ) result -> leftStep k v result) intermediateResult leftovers
```