A set of unique values that when iterated or converted to a list, the order of values 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 Set
that is iterated by the order of insertion.
Create an empty set.
Create a set with one value.
Insert a value into a set.
Remove a value from a set. If the value doesn't exist, no changes are made.
Check if a set is empty.
Check if a value is in a set.
Get the number of values in the set.
Convert a set into a list, sorted by insertion order.
Convert a list into a set, removing any duplicates.
Apply a function to all values in a set.
Fold the values in a set, in insertion order.
Fold the values in a set, in reverse insertion order.
Return a new OrderedSet
that only contains values that satisfy a predicate.
Split a OrderedSet
to a tuple of OrderedSet
. The first contains all
values that satisfy the predicate, and the second contains the rest.
Combine two sets. Keep all values while removing any duplicates.
Combine two sets. Keep values that appear in both sets.
Keep values of the first set that do not appear in the second set.
module OrderedSet
exposing
( OrderedSet
, empty
, singleton
, insert
, remove
, isEmpty
, member
, size
, foldl
, foldr
, map
, filter
, partition
, toList
, fromList
, union
, intersect
, diff
)
{-| A set of unique values that when iterated or converted to a list, the order of
values 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.
# Sets
@docs OrderedSet
# Build
@docs empty, singleton, insert, remove
# Query
@docs isEmpty, member, size
# Lists
@docs toList, fromList
# Transform
@docs map, foldl, foldr, filter, partition
# Combine
@docs union, intersect, diff
-}
import Dict exposing (Dict)
import List
{-| A type of `Set` that is iterated by the order of insertion.
-}
type OrderedSet comparable
= OrderedSet (List comparable) (Dict comparable ())
{-| Create an empty set.
-}
empty : OrderedSet comparable
empty =
OrderedSet [] Dict.empty
{-| Check if a set is empty.
-}
isEmpty : OrderedSet comparable -> Bool
isEmpty oset =
oset == empty
{-| Check if a value is in a set.
-}
member : comparable -> OrderedSet comparable -> Bool
member key (OrderedSet _ dict) =
Dict.member key dict
{-| Get the number of values in the set.
-}
size : OrderedSet comparable -> Int
size (OrderedSet list _) =
List.length list
{-| Create a set with one value.
-}
singleton : comparable -> OrderedSet comparable
singleton key =
insert key empty
{-| Insert a value into a set.
-}
insert : comparable -> OrderedSet comparable -> OrderedSet comparable
insert key (OrderedSet list dict) =
case Dict.get key dict of
Just _ ->
OrderedSet list dict
Nothing ->
OrderedSet (list ++ [ key ]) (Dict.insert key () dict)
{-| Remove a value from a set. If the value doesn't exist,
no changes are made.
-}
remove : comparable -> OrderedSet comparable -> OrderedSet comparable
remove key (OrderedSet list dict) =
case Dict.get key dict of
Just _ ->
OrderedSet (List.filter (\k -> k /= key) list) (Dict.remove key dict)
Nothing ->
OrderedSet list dict
-- TRANSFORM
{-| Apply a function to all values in a set.
-}
map : (comparable -> comparable2) -> OrderedSet comparable -> OrderedSet comparable2
map f (OrderedSet list _) =
fromList <| List.map f list
{-| Fold the values in a set, in insertion order.
-}
foldl : (comparable -> b -> b) -> b -> OrderedSet comparable -> b
foldl f acc (OrderedSet list _) =
List.foldl f acc list
{-| Fold the values in a set, in reverse insertion order.
-}
foldr : (comparable -> b -> b) -> b -> OrderedSet comparable -> b
foldr f acc (OrderedSet list _) =
List.foldr f acc list
{-| Return a new `OrderedSet` that only contains values that satisfy a predicate.
-}
filter :
(comparable -> Bool)
-> OrderedSet comparable
-> OrderedSet comparable
filter predicate (OrderedSet list dict) =
OrderedSet (List.filter predicate list)
(Dict.filter (\k _ -> predicate k) dict)
{-| Split a `OrderedSet` to a tuple of `OrderedSet`. The first contains all
values that satisfy the predicate, and the second contains the rest.
-}
partition :
(comparable -> Bool)
-> OrderedSet comparable
-> ( OrderedSet comparable, OrderedSet comparable )
partition predicate (OrderedSet list dict) =
let
( list1, list2 ) =
List.partition predicate list
( dict1, dict2 ) =
Dict.partition (\k _ -> predicate k) dict
in
( OrderedSet list1 dict1, OrderedSet list2 dict2 )
-- LISTS
{-| Convert a set into a list, sorted by insertion order.
-}
toList : OrderedSet comparable -> List comparable
toList (OrderedSet list _) =
list
{-| Convert a list into a set, removing any duplicates.
-}
fromList : List comparable -> OrderedSet comparable
fromList xs =
List.foldl insert empty xs
-- COMBINE
{-| Combine two sets. Keep all values while removing any duplicates.
-}
union : OrderedSet comparable -> OrderedSet comparable -> OrderedSet comparable
union oset1 oset2 =
let
reducer =
\k acc ->
if member k oset1 then
acc
else
insert k acc
in
foldl reducer oset1 oset2
{-| Combine two sets. Keep values that appear in both sets.
-}
intersect :
OrderedSet comparable
-> OrderedSet comparable
-> OrderedSet comparable
intersect oset1 oset2 =
filter (\k -> member k oset2) oset1
{-| Keep values of the first set that do not appear in the second set.
-}
diff : OrderedSet comparable -> OrderedSet comparable -> OrderedSet comparable
diff oset1 oset2 =
foldl (\k t -> remove k t) oset1 oset2