(.module:
  [library
   [lux {"-" [list]}
    [abstract
     [equivalence {"+" [Equivalence]}]
     [hash {"+" [Hash]}]
     [predicate {"+" [Predicate]}]
     [monoid {"+" [Monoid]}]]
    [data
     [collection
      ["[0]" list ("[1]\[0]" mix)]]]
    [math
     [number
      ["n" nat]]]]]
  ["[0]" // "_"
   ["[1]" dictionary {"+" [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)))
  //.merged)

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

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

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

(implementation: .public (monoid hash)
  (All (_ a) (-> (Hash a) (Monoid (Set a))))

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