blob: 6fd3a46718dc65ca2a5c0bfb41bab4095aa72dc4 (
plain)
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
|
## https://en.wikipedia.org/wiki/Multiset
(.module:
[lux #*
[abstract
[equivalence (#+ Equivalence)]
[hash (#+ Hash)]]
[control
["." function]]
[math
[number
["n" nat]]]
[type
[abstract (#+ abstract: :abstraction :representation ^:representation)]]]
["." //
[//
["." list ("#\." fold monoid)]
["." dictionary (#+ Dictionary)]
[//
["." maybe]]]])
(abstract: #export (Set a)
(Dictionary a Nat)
(def: #export new
(All [a] (-> (Hash a) (Set a)))
(|>> dictionary.new :abstraction))
(def: #export size
(All [a] (-> (Set a) Nat))
(|>> :representation dictionary.values (list\fold n.+ 0)))
(def: #export (add multiplicity elem set)
(All [a] (-> Nat a (Set a) (Set a)))
(case multiplicity
0 set
_ (|> set
:representation
(dictionary.upsert elem 0 (n.+ multiplicity))
:abstraction)))
(def: #export (remove multiplicity elem set)
(All [a] (-> Nat a (Set a) (Set a)))
(case multiplicity
0 set
_ (case (dictionary.get elem (:representation set))
(#.Some current)
(:abstraction
(if (n.> multiplicity current)
(dictionary.update elem (n.- multiplicity) (:representation set))
(dictionary.remove elem (:representation set))))
#.None
set)))
(def: #export (multiplicity set elem)
(All [a] (-> (Set a) a Nat))
(|> set :representation (dictionary.get elem) (maybe.default 0)))
(def: #export to_list
(All [a] (-> (Set a) (List a)))
(|>> :representation
dictionary.entries
(list\fold (function (_ [elem multiplicity] output)
(list\compose (list.repeat multiplicity elem) output))
#.Nil)))
(template [<name> <compose>]
[(def: #export (<name> parameter subject)
(All [a] (-> (Set a) (Set a) (Set a)))
(:abstraction (dictionary.merge_with <compose> (:representation parameter) (:representation subject))))]
[union n.max]
[sum n.+]
)
(def: #export (intersection parameter (^:representation subject))
(All [a] (-> (Set a) (Set a) (Set a)))
(list\fold (function (_ [elem multiplicity] output)
(..add (n.min (..multiplicity parameter elem)
multiplicity)
elem
output))
(..new (dictionary.key_hash subject))
(dictionary.entries subject)))
(def: #export (difference parameter subject)
(All [a] (-> (Set a) (Set a) (Set a)))
(|> parameter
:representation
dictionary.entries
(list\fold (function (_ [elem multiplicity] output)
(..remove multiplicity elem output))
subject)))
(def: #export (sub? reference subject)
(All [a] (-> (Set a) (Set a) Bit))
(|> subject
:representation
dictionary.entries
(list.every? (function (_ [elem multiplicity])
(|> elem
(..multiplicity reference)
(n.>= multiplicity))))))
(def: #export (support set)
(All [a] (-> (Set a) (//.Set a)))
(let [(^@ set [hash _]) (:representation set)]
(|> set
dictionary.keys
(//.from_list hash))))
(structure: #export equivalence
(All [a] (Equivalence (Set a)))
(def: (= (^:representation reference) sample)
(and (n.= (dictionary.size reference)
(dictionary.size (:representation sample)))
(|> reference
dictionary.entries
(list.every? (function (_ [elem multiplicity])
(|> elem
(..multiplicity sample)
(n.= multiplicity))))))))
(structure: #export hash
(All [a] (Hash (Set a)))
(def: &equivalence ..equivalence)
(def: (hash (^:representation set))
(let [[hash _] set]
(list\fold (function (_ [elem multiplicity] acc)
(|> elem (\ hash hash) (n.* multiplicity) (n.+ acc)))
0
(dictionary.entries set)))))
)
(def: #export (member? set elem)
(All [a] (-> (Set a) a Bit))
(|> elem (..multiplicity set) (n.> 0)))
(def: #export empty?
(All [a] (-> (Set a) Bit))
(|>> ..size (n.= 0)))
(def: #export (from_list hash subject)
(All [a] (-> (Hash a) (List a) (Set a)))
(list\fold (..add 1) (..new hash) subject))
(def: #export (from_set subject)
(All [a] (-> (//.Set a) (Set a)))
(..from_list (//.member_hash subject)
(//.to_list subject)))
(def: #export super?
(All [a] (-> (Set a) (Set a) Bit))
(function.flip sub?))
|
