(.module:
  lux
  (lux (control [equivalence #+ Equivalence]
                [hash #+ Hash])
       (data (collection ["dict" dictionary #+ Dictionary]
                         [list "list/" Fold<List>]))
       (type abstract)))

(abstract: #export (Set a)
  {}
  
  (Dictionary a a)

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

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

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

  (def: #export (remove elem set)
    (All [a] (-> a (Set a) (Set a)))
    (|> set :representation (dict.remove elem) :abstraction))

  (def: #export (member? set elem)
    (All [a] (-> (Set a) a Bool))
    (|> set :representation (dict.contains? elem)))

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

  (def: #export (union xs yx)
    (All [a] (-> (Set a) (Set a) (Set a)))
    (:abstraction (dict.merge (:representation xs) (:representation yx))))

  (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)))
    (:abstraction (dict.select (dict.keys (:representation filter))
                               (:representation base))))

  (structure: #export Equivalence<Set> (All [a] (Equivalence (Set a)))
    (def: (= reference sample)
      (let [[Hash<a> _] (:representation reference)]
        (:: (list.Equivalence<List> (get@ #hash.eq Hash<a>)) =
            (..to-list reference) (..to-list sample)))))

  (structure: #export Hash<Set> (All [a] (Hash (Set a)))
    (def: eq ..Equivalence<Set>)
    
    (def: (hash set)
      (let [[Hash<a> _] (:representation set)]
        (list/fold (function (_ elem acc) (n/+ (:: Hash<a> hash elem) acc))
                   +0
                   (..to-list set)))))
  )

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

(def: #export (from-list Hash<a> xs)
  (All [a] (-> (Hash a) (List a) (Set a)))
  (list/fold ..add (..new Hash<a>) xs))

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

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