(.require
 [library
  [lux (.except has list)
   [abstract
    [equivalence (.only Equivalence)]
    [hash (.only Hash)]
    [predicate (.only Predicate)]
    [monoid (.only Monoid)]]
   [data
    [collection
     ["[0]" list (.use "[1]#[0]" mix)]]]
   [macro
    ["^" pattern]]
   [math
    [number
     ["n" nat]]]]]
 ["[0]" //
  ["[1]" dictionary (.only Dictionary)]])

(type: .public (Set a)
  (Dictionary a Any))

(def .public member_hash
  (All (_ a) (-> (Set a) (Hash a)))
  //.key_hash)

(def .public empty
  (All (_ a) (-> (Hash a) (Set a)))
  //.empty)

(def .public size
  (All (_ a) (-> (Set a) Nat))
  //.size)

(def .public (has elem set)
  (All (_ a) (-> a (Set a) (Set a)))
  (|> set (//.has elem [])))

(def .public lacks
  (All (_ a) (-> a (Set a) (Set a)))
  //.lacks)

(def .public member?
  (All (_ a) (-> (Set a) a Bit))
  //.key?)

(def .public list
  (All (_ a) (-> (Set a) (List a)))
  //.keys)

(def .public union
  (All (_ a) (-> (Set a) (Set a) (Set a)))
  //.composite)

(def .public (difference sub base)
  (All (_ a) (-> (Set a) (Set a) (Set a)))
  (list#mix ..lacks base (..list sub)))

(def .public (intersection filter base)
  (All (_ a) (-> (Set a) (Set a) (Set a)))
  (//.sub (//.keys filter)
          base))

(def .public equivalence
  (All (_ a) (Equivalence (Set a)))
  (implementation
   (def (= (^.let reference [hash _]) sample)
     (and (n.= (..size reference)
               (..size sample))
          (list.every? (..member? reference)
                       (..list sample))))))

(def .public hash
  (All (_ a) (Hash (Set a)))
  (implementation
   (def equivalence ..equivalence)
   
   (def (hash set)
     (|> set
         ..list
         (at (list.hash (..member_hash set)) hash)))))

(def .public (monoid hash)
  (All (_ a) (-> (Hash a) (Monoid (Set a))))
  (implementation
   (def identity (..empty hash))
   (def composite ..union)))

(def .public empty?
  (All (_ a) (-> (Set a) Bit))
  (|>> ..size (n.= 0)))

(def .public (of_list hash elements)
  (All (_ a) (-> (Hash a) (List a) (Set a)))
  (list#mix ..has (..empty hash) elements))

(def .public (sub? super sub)
  (All (_ a) (-> (Set a) (Set a) Bit))
  (list.every? (..member? super) (..list sub)))

(def .public (super? sub super)
  (All (_ a) (-> (Set a) (Set a) Bit))
  (..sub? super sub))

(def .public predicate
  (All (_ a) (-> (Set a) (Predicate a)))
  ..member?)