diff options
Diffstat (limited to 'stdlib/source/lux/data/collection/set/multi.lux')
| -rw-r--r-- | stdlib/source/lux/data/collection/set/multi.lux | 165 |
1 files changed, 83 insertions, 82 deletions
diff --git a/stdlib/source/lux/data/collection/set/multi.lux b/stdlib/source/lux/data/collection/set/multi.lux index 9cfd9e4b1..fb9925e98 100644 --- a/stdlib/source/lux/data/collection/set/multi.lux +++ b/stdlib/source/lux/data/collection/set/multi.lux @@ -4,12 +4,13 @@ [abstract [equivalence (#+ Equivalence)] [hash (#+ Hash)]] - ["." function] - [type (#+ :share) - abstract]] + [control + ["." function]] + [type + [abstract (#+ abstract: :abstraction :representation ^:representation)]]] ["." // [// - ["." list ("#;." fold)] + ["." list ("#@." fold monoid)] ["." dictionary (#+ Dictionary)] [// ["." maybe] @@ -25,75 +26,69 @@ (def: #export size (All [a] (-> (Set a) Nat)) - (|>> :representation dictionary.values (list;fold n.+ 0))) + (|>> :representation dictionary.values (list@fold n.+ 0))) - (def: #export (add/* count elem set) + (def: #export (add multiplicity elem set) (All [a] (-> Nat a (Set a) (Set a))) - (|> set :representation (dictionary.update~ elem 0 (n.+ count)) :abstraction)) - - (def: #export add/1 - (All [a] (-> a (Set a) (Set a))) - (add/* 1)) - - (def: #export (remove/* count elem set) + (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 (dictionary.get elem (:representation set)) - (#.Some current) - (let [transform (:share [a] - {(Set a) - set} - {(-> (Dictionary a Nat) (Dictionary a Nat)) - (if (n.> count current) - (dictionary.update elem (n.- count)) - (dictionary.remove elem))})] - (|> set :representation transform :abstraction)) - - #.None - set)) - - (def: #export remove/1 - (All [a] (-> a (Set a) (Set a))) - (remove/* 1)) - - (def: #export (multiplicity elem set) - (All [a] (-> a (Set a) Nat)) + (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))) - (let [append (: (All [a] (-> a Nat (List a) (List a))) - (function (append elem count output) - (case count - 0 output - _ (|> output (#.Cons elem) (append elem (dec count))))))] - (|>> :representation - dictionary.entries - (list;fold (function (_ [elem count] output) - (append elem count output)) - #.Nil)))) - - (def: #export (union parameter subject) + (|>> :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))) - (:abstraction (dictionary.merge-with n.+ (:representation parameter) (:representation subject)))) + (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 count] output) - (remove/* count elem output)) - subject))) - - (def: #export (intersection parameter subject) - (All [a] (-> (Set a) (Set a) (Set a))) - (|> parameter - :representation - dictionary.entries - (list;fold (function (_ [elem count] (^:representation output)) - (:abstraction (if (dictionary.contains? elem output) - (dictionary.update elem (n.min count) output) - output))) + (list@fold (function (_ [elem multiplicity] output) + (..remove multiplicity elem output)) subject))) (def: #export (sub? reference subject) @@ -101,54 +96,60 @@ (|> subject :representation dictionary.entries - (list.every? (function (_ [elem count]) - (|> reference - :representation - (dictionary.get elem) - (maybe.default 0) - (n.>= count)))))) + (list.every? (function (_ [elem multiplicity]) + (|> elem + (..multiplicity reference) + (n.>= multiplicity)))))) (def: #export (support set) (All [a] (-> (Set a) (//.Set a))) - (let [(^@ set [Hash<a> _]) (:representation set)] + (let [(^@ set [hash _]) (:representation set)] (|> set dictionary.keys - (//.from-list Hash<a>)))) + (//.from-list hash)))) - (structure: #export equivalence (All [a] (Equivalence (Set a))) - (def: (= (^:representation reference) (^:representation sample)) + (structure: #export equivalence + (All [a] (Equivalence (Set a))) + + (def: (= (^:representation reference) sample) (and (n.= (dictionary.size reference) - (dictionary.size sample)) + (dictionary.size (:representation sample))) (|> reference dictionary.entries - (list.every? (function (_ [elem count]) - (|> sample - (dictionary.get elem) - (maybe.default 0) - (n.= count)))))))) + (list.every? (function (_ [elem multiplicity]) + (|> elem + (..multiplicity sample) + (n.= multiplicity)))))))) - (structure: #export hash (All [a] (Hash (Set a))) + (structure: #export hash + (All [a] (Hash (Set a))) + (def: &equivalence ..equivalence) (def: (hash (^:representation set)) - (let [[Hash<a> _] set] - (list;fold (function (_ [elem count] acc) - (|> elem (:: Hash<a> hash) (n.* count) (n.+ acc))) + (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)) - (|> set (..multiplicity elem) (n.> 0))) + (|> elem (..multiplicity set) (n.> 0))) (def: #export empty? (All [a] (-> (Set a) Bit)) (|>> ..size (n.= 0))) -(def: #export (from-list Hash<a> subject) +(def: #export (from-list hash subject) (All [a] (-> (Hash a) (List a) (Set a))) - (list;fold ..add/1 (..new Hash<a>) subject)) + (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)) |