A dictionary type that when iterated or converted to a list, the order of entries will be the same as the order they were inserted.
As it uses Dict
under the hood, the keys can only be comparable types, which
include Int
, Float
, Time
, Char
, String
, and tuples or lists of
comparable types.
A type of Dict
that is iterated by the order of insertion.
Create an empty dictionary.
Create a dictionary with one key-value pair.
Insert a key-value pair into a dictionary. Replace the value if the key already exists.
Update the value of a specific key with an updater function.
Since the key may not exist before or after the update, the updater function
takes a Maybe v
and returns a Maybe v
.
Remove a key-value pair from a dictionary. If the key doesn't exist, no changes are made.
Check if a dictionary is empty.
Check if a key is in a dictionary.
Get the value associated with a key. Return Nothing
if the key is not found.
Get the number of key-value pairs in the dictionary.
Get all of the keys in a dictionary, in insertion order.
Get all of the values in a dictionary, in insertion order.
Convert a dictionary into an association list of key-value pairs, in insertion order.
Convert an association list into a dictionary.
Apply a function to all values in a dictionary.
Fold the key-value pairs in a dictionary, in insertion order.
Fold the key-value pairs in a dictionary, in reverse insertion order.
Return a new OrderedDict
that only contains entries that satisfy a predicate.
Split a OrderedDict
to a tuple of OrderedDict
. The first contains all
entries that satisfy the predicate, and the second contains the rest.
Combine two dictionaries. If there is a collision, preference is given to the first dictionary.
union (singleton "x" 1) (singleton "x" 2) == singleton "x" 1
Keep a key-value pair when its key appears in the second dictionary. Preference is given to values in the first dictionary.
Keep a key-value pair when its key does not appear in the second dictionary.
module OrderedDict
exposing
( OrderedDict
, empty
, singleton
, insert
, remove
, update
, isEmpty
, get
, member
, size
, filter
, partition
, foldl
, foldr
, map
, keys
, values
, toList
, fromList
, union
, intersect
, diff
)
{-| A dictionary type that when iterated or converted to a list, the order of
entries will be the same as the order they were inserted.
As it uses `Dict` under the hood, the keys can only be comparable types, which
include `Int`, `Float`, `Time`, `Char`, `String`, and tuples or lists of
comparable types.
# Dictionaries
@docs OrderedDict
# Build
@docs empty, singleton, insert, update, remove
# Query
@docs isEmpty, member, get, size
# Lists
@docs keys, values, toList, fromList
# Transform
@docs map, foldl, foldr, filter, partition
# Combine
@docs union, intersect, diff
-}
import Dict exposing (Dict)
import List
{-| A type of `Dict` that is iterated by the order of insertion.
-}
type OrderedDict comparable v
= OrderedDict (List comparable) (Dict comparable v)
{-| Create an empty dictionary.
-}
empty : OrderedDict comparable v
empty =
OrderedDict [] Dict.empty
{-| Check if a dictionary is empty.
-}
isEmpty : OrderedDict comparable v -> Bool
isEmpty odict =
odict == empty
{-| Get the value associated with a key. Return `Nothing` if the key is not found.
-}
get : comparable -> OrderedDict comparable v -> Maybe v
get key (OrderedDict _ dict) =
Dict.get key dict
{-| Check if a key is in a dictionary.
-}
member : comparable -> OrderedDict comparable v -> Bool
member key (OrderedDict _ dict) =
Dict.member key dict
{-| Get the number of key-value pairs in the dictionary.
-}
size : OrderedDict comparable v -> Int
size (OrderedDict list _) =
List.length list
{-| Create a dictionary with one key-value pair.
-}
singleton : comparable -> v -> OrderedDict comparable v
singleton key value =
insert key value empty
{-| Insert a key-value pair into a dictionary. Replace the value if the key
already exists.
-}
insert : comparable -> v -> OrderedDict comparable v -> OrderedDict comparable v
insert key value odict =
update key (always (Just value)) odict
{-| Remove a key-value pair from a dictionary. If the key doesn't exist,
no changes are made.
-}
remove : comparable -> OrderedDict comparable v -> OrderedDict comparable v
remove key odict =
update key (always Nothing) odict
{-| Update the value of a specific key with an updater function.
Since the key may not exist before or after the update, the updater function
takes a `Maybe v` and returns a `Maybe v`.
-}
update :
comparable
-> (Maybe v -> Maybe v)
-> OrderedDict comparable v
-> OrderedDict comparable v
update key updater (OrderedDict list dict) =
let
newDict =
Dict.update key updater dict
newList =
case updater (Dict.get key dict) of
Just _ ->
if List.member key list then
list
else
list ++ [ key ]
Nothing ->
if List.member key list then
List.filter (\k -> k /= key) list
else
list
in
OrderedDict newList newDict
-- TRANSFORM
{-| Apply a function to all values in a dictionary.
-}
map : (comparable -> a -> b) -> OrderedDict comparable a -> OrderedDict comparable b
map f (OrderedDict list dict) =
OrderedDict list (Dict.map f dict)
reducer :
Dict comparable v
-> (comparable -> v -> b -> b)
-> (comparable -> b -> b)
reducer dict f =
\key acc ->
case Dict.get key dict of
Just value ->
f key value acc
Nothing ->
acc
{-| Fold the key-value pairs in a dictionary, in insertion order.
-}
foldl : (comparable -> v -> b -> b) -> b -> OrderedDict comparable v -> b
foldl f acc (OrderedDict list dict) =
List.foldl (reducer dict f) acc list
{-| Fold the key-value pairs in a dictionary, in reverse insertion order.
-}
foldr : (comparable -> v -> b -> b) -> b -> OrderedDict comparable v -> b
foldr f acc (OrderedDict list dict) =
List.foldr (reducer dict f) acc list
{-| Return a new `OrderedDict` that only contains entries that satisfy a predicate.
-}
filter :
(comparable -> v -> Bool)
-> OrderedDict comparable v
-> OrderedDict comparable v
filter predicate dictionary =
let
add key value odict =
if predicate key value then
insert key value odict
else
odict
in
foldl add empty dictionary
{-| Split a `OrderedDict` to a tuple of `OrderedDict`. The first contains all
entries that satisfy the predicate, and the second contains the rest.
-}
partition :
(comparable -> v -> Bool)
-> OrderedDict comparable v
-> ( OrderedDict comparable v, OrderedDict comparable v )
partition predicate dictionary =
let
add key value ( odict1, odict2 ) =
if predicate key value then
( insert key value odict1, odict2 )
else
( odict1, insert key value odict2 )
in
foldl add ( empty, empty ) dictionary
-- LISTS
{-| Get all of the keys in a dictionary, in insertion order.
-}
keys : OrderedDict comparable v -> List comparable
keys (OrderedDict list _) =
list
{-| Get all of the values in a dictionary, in insertion order.
-}
values : OrderedDict comparable v -> List v
values (OrderedDict list dict) =
List.filterMap (\key -> Dict.get key dict) list
{-| Convert a dictionary into an association list of key-value pairs, in insertion order.
-}
toList : OrderedDict comparable v -> List ( comparable, v )
toList (OrderedDict list dict) =
List.map2 (,) list (values <| OrderedDict list dict)
{-| Convert an association list into a dictionary.
-}
fromList : List ( comparable, v ) -> OrderedDict comparable v
fromList assocs =
let
( list, _ ) =
List.unzip assocs
dict =
Dict.fromList assocs
in
OrderedDict list dict
-- COMBINE
{-| Combine two dictionaries. If there is a collision, preference is given
to the first dictionary.
union (singleton "x" 1) (singleton "x" 2) == singleton "x" 1
-}
union : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v
union odict1 odict2 =
let
reducer =
\k v acc ->
if member k odict1 then
acc
else
insert k v acc
in
foldl reducer odict1 odict2
{-| Keep a key-value pair when its key appears in the second dictionary.
Preference is given to values in the first dictionary.
-}
intersect :
OrderedDict comparable v
-> OrderedDict comparable v
-> OrderedDict comparable v
intersect odict1 odict2 =
filter (\k _ -> member k odict2) odict1
{-| Keep a key-value pair when its key does not appear in the second dictionary.
-}
diff : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v
diff odict1 odict2 =
foldl (\k v t -> remove k t) odict1 odict2