diff options
Diffstat (limited to 'stdlib/source/library/lux/data/collection/set')
-rw-r--r-- | stdlib/source/library/lux/data/collection/set/multi.lux | 222 | ||||
-rw-r--r-- | stdlib/source/library/lux/data/collection/set/ordered.lux | 116 |
2 files changed, 167 insertions, 171 deletions
diff --git a/stdlib/source/library/lux/data/collection/set/multi.lux b/stdlib/source/library/lux/data/collection/set/multi.lux index f3df37d57..cd36648eb 100644 --- a/stdlib/source/library/lux/data/collection/set/multi.lux +++ b/stdlib/source/library/lux/data/collection/set/multi.lux @@ -19,122 +19,120 @@ ["[0]" dictionary {"+" [Dictionary]}]]]) (abstract: .public (Set a) - {} - (Dictionary a Nat) - (def: .public empty - (All (_ a) (-> (Hash a) (Set a))) - (|>> dictionary.empty :abstraction)) - - (def: .public size - (All (_ a) (-> (Set a) Nat)) - (|>> :representation dictionary.values (list\mix n.+ 0))) - - (def: .public (has multiplicity elem set) - (All (_ a) (-> Nat a (Set a) (Set a))) - (case multiplicity - 0 set - _ (|> set - :representation - (dictionary.revised' elem 0 (n.+ multiplicity)) - :abstraction))) - - (def: .public (lacks multiplicity elem set) - (All (_ a) (-> Nat a (Set a) (Set a))) - (case multiplicity - 0 set - _ (case (dictionary.value elem (:representation set)) - (#.Some current) - (:abstraction - (if (n.> multiplicity current) - (dictionary.revised elem (n.- multiplicity) (:representation set)) - (dictionary.lacks elem (:representation set)))) - - #.None - set))) - - (def: .public (multiplicity set elem) - (All (_ a) (-> (Set a) a Nat)) - (|> set :representation (dictionary.value elem) (maybe.else 0))) - - (def: .public list - (All (_ a) (-> (Set a) (List a))) - (|>> :representation + [(def: .public empty + (All (_ a) (-> (Hash a) (Set a))) + (|>> dictionary.empty :abstraction)) + + (def: .public size + (All (_ a) (-> (Set a) Nat)) + (|>> :representation dictionary.values (list\mix n.+ 0))) + + (def: .public (has multiplicity elem set) + (All (_ a) (-> Nat a (Set a) (Set a))) + (case multiplicity + 0 set + _ (|> set + :representation + (dictionary.revised' elem 0 (n.+ multiplicity)) + :abstraction))) + + (def: .public (lacks multiplicity elem set) + (All (_ a) (-> Nat a (Set a) (Set a))) + (case multiplicity + 0 set + _ (case (dictionary.value elem (:representation set)) + (#.Some current) + (:abstraction + (if (n.> multiplicity current) + (dictionary.revised elem (n.- multiplicity) (:representation set)) + (dictionary.lacks elem (:representation set)))) + + #.None + set))) + + (def: .public (multiplicity set elem) + (All (_ a) (-> (Set a) a Nat)) + (|> set :representation (dictionary.value elem) (maybe.else 0))) + + (def: .public list + (All (_ a) (-> (Set a) (List a))) + (|>> :representation + dictionary.entries + (list\mix (function (_ [elem multiplicity] output) + (list\composite (list.repeated multiplicity elem) output)) + #.End))) + + (template [<name> <composite>] + [(def: .public (<name> parameter subject) + (All (_ a) (-> (Set a) (Set a) (Set a))) + (:abstraction (dictionary.merged_with <composite> (:representation parameter) (:representation subject))))] + + [union n.max] + [sum n.+] + ) + + (def: .public (intersection parameter (^:representation subject)) + (All (_ a) (-> (Set a) (Set a) (Set a))) + (list\mix (function (_ [elem multiplicity] output) + (..has (n.min (..multiplicity parameter elem) + multiplicity) + elem + output)) + (..empty (dictionary.key_hash subject)) + (dictionary.entries subject))) + + (def: .public (difference parameter subject) + (All (_ a) (-> (Set a) (Set a) (Set a))) + (|> parameter + :representation dictionary.entries (list\mix (function (_ [elem multiplicity] output) - (list\composite (list.repeated multiplicity elem) output)) - #.End))) - - (template [<name> <composite>] - [(def: .public (<name> parameter subject) - (All (_ a) (-> (Set a) (Set a) (Set a))) - (:abstraction (dictionary.merged_with <composite> (:representation parameter) (:representation subject))))] - - [union n.max] - [sum n.+] - ) - - (def: .public (intersection parameter (^:representation subject)) - (All (_ a) (-> (Set a) (Set a) (Set a))) - (list\mix (function (_ [elem multiplicity] output) - (..has (n.min (..multiplicity parameter elem) - multiplicity) - elem - output)) - (..empty (dictionary.key_hash subject)) - (dictionary.entries subject))) - - (def: .public (difference parameter subject) - (All (_ a) (-> (Set a) (Set a) (Set a))) - (|> parameter - :representation - dictionary.entries - (list\mix (function (_ [elem multiplicity] output) - (..lacks multiplicity elem output)) - subject))) - - (def: .public (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: .public (support set) - (All (_ a) (-> (Set a) (//.Set a))) - (let [(^@ set [hash _]) (:representation set)] - (|> set - dictionary.keys - (//.of_list hash)))) - - (implementation: .public 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)))))))) - - (implementation: .public hash - (All (_ a) (Hash (Set a))) - - (def: &equivalence ..equivalence) - - (def: (hash (^:representation set)) - (let [[hash _] set] - (list\mix (function (_ [elem multiplicity] acc) - (|> elem (\ hash hash) (n.* multiplicity) (n.+ acc))) - 0 - (dictionary.entries set))))) + (..lacks multiplicity elem output)) + subject))) + + (def: .public (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: .public (support set) + (All (_ a) (-> (Set a) (//.Set a))) + (let [(^@ set [hash _]) (:representation set)] + (|> set + dictionary.keys + (//.of_list hash)))) + + (implementation: .public 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)))))))) + + (implementation: .public hash + (All (_ a) (Hash (Set a))) + + (def: &equivalence ..equivalence) + + (def: (hash (^:representation set)) + (let [[hash _] set] + (list\mix (function (_ [elem multiplicity] acc) + (|> elem (\ hash hash) (n.* multiplicity) (n.+ acc))) + 0 + (dictionary.entries set)))))] ) (def: .public (member? set elem) diff --git a/stdlib/source/library/lux/data/collection/set/ordered.lux b/stdlib/source/library/lux/data/collection/set/ordered.lux index 91edd4642..a3bd77830 100644 --- a/stdlib/source/library/lux/data/collection/set/ordered.lux +++ b/stdlib/source/library/lux/data/collection/set/ordered.lux @@ -13,67 +13,65 @@ abstract]]]) (abstract: .public (Set a) - {} - (/.Dictionary a a) - (def: .public empty - (All (_ a) (-> (Order a) (Set a))) - (|>> /.empty :abstraction)) - - (def: .public (member? set elem) - (All (_ a) (-> (Set a) a Bit)) - (/.key? (:representation set) elem)) - - (template [<type> <name> <alias>] - [(def: .public <name> - (All (_ a) (-> (Set a) <type>)) - (|>> :representation <alias>))] - - [(Maybe a) min /.min] - [(Maybe a) max /.max] - [Nat size /.size] - [Bit empty? /.empty?] - ) - - (def: .public (has elem set) - (All (_ a) (-> a (Set a) (Set a))) - (|> set :representation (/.has elem elem) :abstraction)) - - (def: .public (lacks elem set) - (All (_ a) (-> a (Set a) (Set a))) - (|> set :representation (/.lacks elem) :abstraction)) - - (def: .public list - (All (_ a) (-> (Set a) (List a))) - (|>> :representation /.keys)) - - (def: .public (of_list &order list) - (All (_ a) (-> (Order a) (List a) (Set a))) - (list\mix has (..empty &order) list)) - - (def: .public (union left right) - (All (_ a) (-> (Set a) (Set a) (Set a))) - (list\mix ..has right (..list left))) - - (def: .public (intersection left right) - (All (_ a) (-> (Set a) (Set a) (Set a))) - (|> (..list right) - (list.only (..member? left)) - (..of_list (value@ #/.&order (:representation right))))) - - (def: .public (difference param subject) - (All (_ a) (-> (Set a) (Set a) (Set a))) - (|> (..list subject) - (list.only (|>> (..member? param) not)) - (..of_list (value@ #/.&order (:representation subject))))) - - (implementation: .public equivalence - (All (_ a) (Equivalence (Set a))) - - (def: (= reference sample) - (\ (list.equivalence (\ (:representation reference) &equivalence)) - = (..list reference) (..list sample)))) + [(def: .public empty + (All (_ a) (-> (Order a) (Set a))) + (|>> /.empty :abstraction)) + + (def: .public (member? set elem) + (All (_ a) (-> (Set a) a Bit)) + (/.key? (:representation set) elem)) + + (template [<type> <name> <alias>] + [(def: .public <name> + (All (_ a) (-> (Set a) <type>)) + (|>> :representation <alias>))] + + [(Maybe a) min /.min] + [(Maybe a) max /.max] + [Nat size /.size] + [Bit empty? /.empty?] + ) + + (def: .public (has elem set) + (All (_ a) (-> a (Set a) (Set a))) + (|> set :representation (/.has elem elem) :abstraction)) + + (def: .public (lacks elem set) + (All (_ a) (-> a (Set a) (Set a))) + (|> set :representation (/.lacks elem) :abstraction)) + + (def: .public list + (All (_ a) (-> (Set a) (List a))) + (|>> :representation /.keys)) + + (def: .public (of_list &order list) + (All (_ a) (-> (Order a) (List a) (Set a))) + (list\mix has (..empty &order) list)) + + (def: .public (union left right) + (All (_ a) (-> (Set a) (Set a) (Set a))) + (list\mix ..has right (..list left))) + + (def: .public (intersection left right) + (All (_ a) (-> (Set a) (Set a) (Set a))) + (|> (..list right) + (list.only (..member? left)) + (..of_list (value@ #/.&order (:representation right))))) + + (def: .public (difference param subject) + (All (_ a) (-> (Set a) (Set a) (Set a))) + (|> (..list subject) + (list.only (|>> (..member? param) not)) + (..of_list (value@ #/.&order (:representation subject))))) + + (implementation: .public equivalence + (All (_ a) (Equivalence (Set a))) + + (def: (= reference sample) + (\ (list.equivalence (\ (:representation reference) &equivalence)) + = (..list reference) (..list sample))))] ) (def: .public (sub? super sub) |