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

(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?
  (All [a] (-> (Set a) a Bit))
  //.key?)

(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)
    (|> set
        ..to_list
        (\ (list.hash (..member_hash set)) hash))))

(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?)