(.module:
  [library
   [lux (#- list)
    [abstract
     [equivalence (#+ Equivalence)]
     [order (#+ Order)]]
    [data
     [collection
      ["." list ("#\." fold)]
      [dictionary
       ["/" ordered]]]]
    [type
     abstract]]])

(abstract: .public (Set a)
  {#.doc (example "A set with ordered entries.")}

  (/.Dictionary a a)

  (def: .public empty
    (All [a] (-> (Order a) (Set a)))
    (|>> /.empty :abstraction))

  (def: .public (member? set elem)
    (All [a] (-> (Set a) a Bit))
    (/.key? (:representation set) elem))

  (template [<type> <name> <alias>]
    [(def: .public <name>
       (All [a] (-> (Set a) <type>))
       (|>> :representation <alias>))]

    [(Maybe a) min /.min]
    [(Maybe a) max /.max]
    [Nat size  /.size]
    [Bit empty? /.empty?]
    )

  (def: .public (add elem set)
    (All [a] (-> a (Set a) (Set a)))
    (|> set :representation (/.put elem elem) :abstraction))

  (def: .public (remove elem set)
    (All [a] (-> a (Set a) (Set a)))
    (|> set :representation (/.remove elem) :abstraction))

  (def: .public list
    (All [a] (-> (Set a) (List a)))
    (|>> :representation /.keys))

  (def: .public (of_list &order list)
    (All [a] (-> (Order a) (List a) (Set a)))
    (list\fold add (..empty &order) list))

  (def: .public (union left right)
    (All [a] (-> (Set a) (Set a) (Set a)))
    (list\fold ..add right (..list left)))

  (def: .public (intersection left right)
    (All [a] (-> (Set a) (Set a) (Set a)))
    (|> (..list right)
        (list.only (..member? left))
        (..of_list (get@ #/.&order (:representation right)))))

  (def: .public (difference param subject)
    (All [a] (-> (Set a) (Set a) (Set a)))
    (|> (..list subject)
        (list.only (|>> (..member? param) not))
        (..of_list (get@ #/.&order (:representation subject)))))

  (implementation: .public equivalence
    (All [a] (Equivalence (Set a)))
    
    (def: (= reference sample)
      (\ (list.equivalence (\ (:representation reference) &equivalence))
         = (..list reference) (..list sample))))
  )

(def: .public (sub? super sub)
  {#.doc (example "Is 'sub' a sub-set of 'super'?")}
  (All [a] (-> (Set a) (Set a) Bit))
  (|> sub
      ..list
      (list.every? (..member? super))))

(def: .public (super? sub super)
  {#.doc (example "Is 'super' a super-set of 'sub'?")}
  (All [a] (-> (Set a) (Set a) Bit))
  (sub? super sub))