(.module:
  [lux #*
   [abstract
    [equivalence (#+ Equivalence)]
    [predicate (#+ Predicate)]
    [monoid (#+ Monoid)]
    ["." hash (#+ Hash)]]
   [data
    [number
     ["n" nat]]
    [collection
     ["//" dictionary (#+ Dictionary)]
     ["." list ("#@." fold)]]]])

(type: #export (Set a)
  (Dictionary a Any))

(def: #export member-hash
  (All [a] (-> (Set a) (Hash a)))
  //.key-hash)

(def: #export new
  (All [a] (-> (Hash a) (Set a)))
  //.new)

(def: #export size
  (All [a] (-> (Set a) Nat))
  //.size)

(def: #export (add elem set)
  (All [a] (-> a (Set a) (Set a)))
  (|> set (//.put elem [])))

(def: #export remove
  (All [a] (-> a (Set a) (Set a)))
  //.remove)

(def: #export (member? set elem)
  (All [a] (-> (Set a) a Bit))
  (//.contains? elem set))

(def: #export to-list
  (All [a] (-> (Set a) (List a)))
  //.keys)

(def: #export union
  (All [a] (-> (Set a) (Set a) (Set a)))
  //.merge)

(def: #export (difference sub base)
  (All [a] (-> (Set a) (Set a) (Set a)))
  (list@fold ..remove base (..to-list sub)))

(def: #export (intersection filter base)
  (All [a] (-> (Set a) (Set a) (Set a)))
  (//.select (//.keys filter)
             base))

(structure: #export equivalence
  (All [a] (Equivalence (Set a)))
  
  (def: (= (^@ reference [hash _]) sample)
    (and (n.= (..size reference)
              (..size sample))
         (list.every? (..member? reference)
                      (..to-list sample)))))

(structure: #export hash
  (All [a] (Hash (Set a)))
  
  (def: &equivalence ..equivalence)
  
  (def: (hash (^@ set [hash _]))
    (list@fold (function (_ elem acc) (n.+ (:: hash hash elem) acc))
               0
               (..to-list set))))

(structure: #export (monoid hash)
  (All [a] (-> (Hash a) (Monoid (Set a))))

  (def: identity (..new hash))
  (def: compose ..union))

(def: #export empty?
  (All [a] (-> (Set a) Bit))
  (|>> ..size (n.= 0)))

(def: #export (from-list hash elements)
  (All [a] (-> (Hash a) (List a) (Set a)))
  (list@fold ..add (..new hash) elements))

(def: #export (sub? super sub)
  (All [a] (-> (Set a) (Set a) Bit))
  (list.every? (..member? super) (..to-list sub)))

(def: #export (super? sub super)
  (All [a] (-> (Set a) (Set a) Bit))
  (..sub? super sub))

(def: #export predicate
  (All [a] (-> (Set a) (Predicate a)))
  ..member?)