git.iko.soy/elk
on 89bbbb9 help sign in
elk/libraries/Set.elm
102 lines 3.0 kB history raw
2module Set
3 ( Set
4 , empty, singleton, insert, remove
5 , member
6 , foldl, foldr, map
7 , filter, partition
8 , union, intersect, diff
9 , toList, fromList
10 ) where
12{-| A set of unique values. The values can be any comparable type. This
13includes `Int`, `Float`, `Time`, `Char`, `String`, and tuples or lists
14of comparable types.
16Insert, remove, and query operations all take *O(log n)* time.
18# Build
19@docs empty, singleton, insert, remove
21# Query
22@docs member
24# Combine
25@docs union, intersect, diff
27# Lists
28@docs toList, fromList
30# Transform
31@docs map, foldl, foldr, filter, partition
33-}
35import Maybe (Maybe)
36import Dict as Dict
37import List as List
39type Set t = Dict.Dict t ()
41{-| Create an empty set. -}
42empty : Set comparable
43empty = Dict.empty
45{-| Create a set with one value. -}
46singleton : comparable -> Set comparable
47singleton k = Dict.singleton k ()
49{-| Insert a value into a set. -}
50insert : comparable -> Set comparable -> Set comparable
51insert k = Dict.insert k ()
53{-| Remove a value from a set. If the value is not found, no changes are made.
54-}
55remove : comparable -> Set comparable -> Set comparable
56remove = Dict.remove
58{-| Determine if a value is in a set. -}
59member : comparable -> Set comparable -> Bool
60member = Dict.member
62{-| Get the union of two sets. Keep all values. -}
63union : Set comparable -> Set comparable -> Set comparable
64union = Dict.union
66{-| Get the intersection of two sets. Keeps values that appear in both sets. -}
67intersect : Set comparable -> Set comparable -> Set comparable
68intersect = Dict.intersect
70{-| Get the difference between the first set and the second. Keeps values
71that do not appear in the second set. -}
72diff : Set comparable -> Set comparable -> Set comparable
73diff = Dict.diff
75{-| Convert a set into a list. -}
76toList : Set comparable -> [comparable]
77toList = Dict.keys
79{-| Convert a list into a set, removing any duplicates. -}
80fromList : [comparable] -> Set comparable
81fromList xs = List.foldl insert empty xs
83{-| Fold over the values in a set, in order from lowest to highest. -}
84foldl : (comparable -> b -> b) -> b -> Set comparable -> b
85foldl f b s = Dict.foldl (\k _ b -> f k b) b s
87{-| Fold over the values in a set, in order from highest to lowest. -}
88foldr : (comparable -> b -> b) -> b -> Set comparable -> b
89foldr f b s = Dict.foldr (\k _ b -> f k b) b s
91{-| Map a function onto a set, creating a new set with no duplicates. -}
92map : (comparable -> comparable') -> Set comparable -> Set comparable'
93map f s = fromList (List.map f (toList s))
95{-| Create a new set consisting only of elements which satisfy a predicate. -}
96filter : (comparable -> Bool) -> Set comparable -> Set comparable
97filter p set = Dict.filter (\k _ -> p k) set
99{-| Create two new sets; the first consisting of elements which satisfy a
100predicate, the second consisting of elements which do not. -}
101partition : (comparable -> Bool) -> Set comparable -> (Set comparable, Set comparable)
102partition p set = Dict.partition (\k _ -> p k) set