git.iko.soy/elk
on 63243ca help sign in
elk/libraries/Set.elm
90 lines 2.5 kB history raw
2module Set (empty,singleton,insert,remove
3 ,member
4 ,foldl,foldr,map
5 ,union,intersect,diff
6 ,toList,fromList
7 ) where
9{-| A set of unique values. The values can be any comparable type. This
10includes `Int`, `Float`, `Time`, `Char`, `String`, and tuples or lists
11of comparable types.
13Insert, remove, and query operations all take *O(log n)* time.
15# Build
16@docs empty, singleton, insert, remove
18# Query
19@docs member
21# Combine
22@docs union, intersect, diff
24# Lists
25@docs toList, fromList
27# Transform
28@docs map, foldl, foldr
30-}
32import Maybe (Maybe)
33import Dict as Dict
34import List as List
36type Set t = Dict.Dict t ()
38{-| Create an empty set. -}
39empty : Set comparable
40empty = Dict.empty
42{-| Create a set with one value. -}
43singleton : comparable -> Set comparable
44singleton k = Dict.singleton k ()
46{-| Insert a value into a set. -}
47insert : comparable -> Set comparable -> Set comparable
48insert k = Dict.insert k ()
50{-| Remove a value from a set. If the value is not found, no changes are made.
51-}
52remove : comparable -> Set comparable -> Set comparable
53remove = Dict.remove
55{-| Determine if a value is in a set. -}
56member : comparable -> Set comparable -> Bool
57member = Dict.member
59{-| Get the union of two sets. Keep all values. -}
60union : Set comparable -> Set comparable -> Set comparable
61union = Dict.union
63{-| Get the intersection of two sets. Keeps values that appear in both sets. -}
64intersect : Set comparable -> Set comparable -> Set comparable
65intersect = Dict.intersect
67{-| Get the difference between the first set and the second. Keeps values
68that do not appear in the second set. -}
69diff : Set comparable -> Set comparable -> Set comparable
70diff = Dict.diff
72{-| Convert a set into a list. -}
73toList : Set comparable -> [comparable]
74toList = Dict.keys
76{-| Convert a list into a set, removing any duplicates. -}
77fromList : [comparable] -> Set comparable
78fromList xs = List.foldl insert empty xs
80{-| Fold over the values in a set, in order from lowest to highest. -}
81foldl : (comparable -> b -> b) -> b -> Set comparable -> b
82foldl f b s = Dict.foldl (\k _ b -> f k b) b s
84{-| Fold over the values in a set, in order from highest to lowest. -}
85foldr : (comparable -> b -> b) -> b -> Set comparable -> b
86foldr f b s = Dict.foldr (\k _ b -> f k b) b s
88{-| Map a function onto a set, creating a new set with no duplicates. -}
89map : (comparable -> comparable') -> Set comparable -> Set comparable'
90map f s = fromList (List.map f (toList s))