elm-oottp/src/ListBackedSet.elm at master · z5h/elm-oottp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
module ListBackedSet exposing (..)


type alias Set a =
    { list : List a }


{-| Create an empty set.
-}
empty : Set a
empty =
    { list = [] }


{-| Create a set with one value.
-}
singleton : a -> Set a
singleton k =
    { list = [ k ] }


{-| Insert a value into a set.
-}
insert : a -> Set a -> Set a
insert k s =
    s |> remove k |> \s -> { list = k :: s.list }


{-| Remove a value from a set. If the value is not found, no changes are made.
-}
remove : a -> Set a -> Set a
remove k s =
    { list = List.filter ((/=) k) s.list }


{-| Determine if a set is empty.
-}
isEmpty : Set a -> Bool
isEmpty { list } =
    List.isEmpty list


{-| Determine if a value is in a set.
-}
member : a -> Set a -> Bool
member k { list } =
    List.member k list


{-| Determine the number of elements in a set.
-}
size : Set a -> Int
size { list } =
    List.length list


{-| Get the union of two sets. Keep all values.
-}
union : Set a -> Set a -> Set a
union s1 s2 =
    fromList (s1.list ++ s2.list)


{-| Get the intersection of two sets. Keeps values that appear in both sets.
-}
intersect : Set a -> Set a -> Set a
intersect set1 set2 =
    filter ((flip member) set2) set1


{-| Get the difference between the first set and the second. Keeps values
that do not appear in the second set.
-}
diff : Set a -> Set a -> Set a
diff set1 set2 =
    filter (((flip member) set2) >> not) set1


{-| Convert a set into a list, sorted from lowest to highest.
-}
toList : Set a -> List a
toList { list } =
    list


{-| Convert a list into a set, removing any duplicates.
-}
fromList : List a -> Set a
fromList xs =
    List.foldr insert empty xs


{-| Fold over the values in a set, in order from lowest to highest.
-}
foldl : (a -> b -> b) -> b -> Set a -> b
foldl f b { list } =
    List.foldl f b list


{-| Fold over the values in a set, in order from highest to lowest.
-}
foldr : (a -> b -> b) -> b -> Set a -> b
foldr f b { list } =
    List.foldr f b list


{-| Map a function onto a set, creating a new set with no duplicates.
-}
map : (a -> b) -> Set a -> Set b
map f s =
    fromList (List.map f (toList s))


{-| Create a new set consisting only of elements which satisfy a predicate.
-}
filter : (a -> Bool) -> Set a -> Set a
filter p { list } =
    fromList (List.filter p list)


cartesianProduct : List x -> List y -> List ( x, y )
cartesianProduct xs ys =
    List.concatMap (\x -> List.map (\y -> ( x, y )) ys) xs


product : Set x -> Set y -> Set ( x, y )
product xs ys =
    cartesianProduct (toList xs) (toList ys)
        |> \list -> { list = list }


{-| Create two new sets; the first consisting of elements which satisfy a
predicate, the second consisting of elements which do not.
-}
partition : (a -> Bool) -> Set a -> ( Set a, Set a )
partition p { list } =
    let
        ( p1, p2 ) =
            List.partition p list
    in
        ( fromList p1, fromList p2 )