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