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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
module Data.Set where
import Prelude hiding (filter,foldl,foldr,null,map,take,drop,splitAt,empty)
import qualified Data.List as List
import qualified Data.Foldable as F
-- This should at the minimum allow adding and removing elements, and
-- holding identical elements at most once.
-- I'm not sure I can effectively use Ord without type classes.
-- Could maybe implement a builtin_compare function that handles
-- Int, Double, LogDouble, Char, String, List, Tuples
data Set a = Set [a]
empty = Set []
singleton x = Set [x]
fromList xs = Set (nub xs)
fromAscList xs = fromList xs
fromDescList xs = fromList xs
fromDistinctAscList xs = fromList xs
fromDistinctDescList xs = fromList xs
powerSet (Set []) = Set [[]]
powerSet (Set (x:xs)) = let Set ys = powerSet (Set xs)
in Set (ys++(List.map (x:) ys))
insert x s@(Set xs) | member x s = s
| otherwise = Set (x:xs)
delete x s@(Set xs) = Set $ List.filter (/=x) xs
member x s@(Set xs) | elem x xs = True
| otherwise = False
notMember x s = not $ member x s
-- lookupLT
-- lookupGT
-- lookupLE
-- lookupGE
null (Set []) = True
null _ = False
size (Set xs) = length xs
isSubsetOf (Set []) s2 = True
isSubsetOf (Set xs) (Set ys) = go xs ys where
go [] ys = True
go (x:xs) ys | x `elem` ys = go xs ys
| otherwise = False
isProperSubsetOf s1 s2 | isSubsetOf s1 s2 = size s1 < size s2
| otherwise = False
disjoint s1 s2 = size (intersection s1 s2) == 0
union (Set xs) (Set ys) = Set (xs ++ List.filter (`notElem` xs) ys)
unions = List.foldl union empty
difference (Set xs) (Set ys) = Set $ List.filter (`notElem` ys) xs
infixl 9 \\
s1 \\ s2 = s1 `difference` s2
intersection (Set xs) (Set ys) = Set $ List.filter (`elem` ys) xs
cartesionProduct (Set xs) (Set ys) = Set [(x,y) | x <- xs, y <- ys]
disjointUnion xs ys = map Left xs `union` map Right ys
filter pred xs = Set $ List.filter pred xs
-- takeWhileAntitone
-- dropWhileAntitone
-- spanAntitone
-- partition
-- split
-- splitMember
-- splitRoot
-- lookupIndex
-- findIndex
-- lookupIndex
-- findIndex
-- elemAt
-- deleteAt
-- take n (Set xs) =
-- drop
-- splitAt
map f (Set xs) = Set $ List.map f xs
-- mapMonotonic
-- foldr
-- foldl
--foldr'
--foldl'
--fold
--lookupMin
--lookupMax
--findMin
--findMax
--deleteMin
--deleteMax
--deleteFindMin
--deleteFindMax
--maxView
-- minView
elems = toAscList
toList (Set xs) = xs
toAscList (Set xs) = List.sort xs
toDescList = reverse . toAscList
instance Show a => Show (Set a) where
show (Set xs) = "Set " ++ show xs
instance F.Foldable Set where
toList (Set xs) = xs
|
