set support

[shriram]

For some assignments it's useful to have sets. E.g., for type-inference, you ideally want a set of constraints, not a list (since the order is meaningless).

Below is support code we're using in my class. Authored by Zach Espiritu and the TA crew of Brown CSCI 1730, Fall 2020. The Pick interface is how we expose set choice in Pyret (where the implementation actually randomizes which item is removed, to avoid code becoming dependent on the implementation).

; Set operations.

; Type for immutable sets.
(define-type-alias (Setof 'a) (Hashof 'a Boolean))

; Convenience definition to create an empty set.
(define empty-set (hash (list)))

; Returns a (Setof 'a) containing all of the elements in the input (Listof 'a).
(define (list->set [items : (Listof 'a)]): (Setof 'a)
  (hash
    (map (lambda ([item : 'a]): ('a * Boolean)
           (pair item #t)) items)))

; Returns a (Listof 'a) containing all of the elements in the input (Setof 'a).
(define (set->list [set : (Setof 'a)]): (Listof 'a)
  (hash-keys set))

; Convenience macro equivalent to the built-in (list ...) macro, but for
; creating (Setof 'a)'s.
(define-syntax set
  (syntax-rules ()
    [(set) (list->set empty)]
    [(set args ...) (list->set (list args ...))]))

; Returns true if `set` contains no elements; otherwise, returns false.
(define (set-empty? [set : (Setof 'a)]): Boolean
  (empty? (set->list set)))

; Returns the number of elements in the input (Setof 'a).
(define (set-count [set : (Setof 'a)]): Number
  (length (set->list set)))

; Returns true if `set` contains `thing`; otherwise, returns false.
(define (set-member? [set : (Setof 'a)] [thing : 'a]): Boolean
  (type-case (Optionof Boolean) (hash-ref set thing)
    [(some v) #t]
    [(none) #f]))

; Returns a new, immutable (Setof 'a) containing all of the elements in `set`
; plus the element `thing`.
(define (set-add [set : (Setof 'a)] [thing : 'a]): (Setof 'a)
  (hash-set set thing #t))

; Returns a new, immutable (Setof 'a) containing all of the elements in `set`
; except the element `thing`.
(define (set-remove [set : (Setof 'a)] [thing : 'a]): (Setof 'a)
  (hash-remove set thing))

; The return type of the `set-pick` function.
(define-type (Pick 'a)
  (pick-none)
  (pick-some [element : 'a] [rest : (Setof 'a)]))

; Picks an arbitrary element out of the input (Setof 'a) and returns a
; (Pick 'a) structure.
(define (set-pick [set : (Setof 'a)]): (Pick 'a)
  (type-case (Listof 'a) (set->list set)
    [empty (pick-none)]
    [(cons item rst-items) (pick-some item (set-remove set item))]))

; Returns a new, immutable (Setof 'a) containing all of the elements in
; `left-set` and all of the elements in `right-set`.
(define (set-union [left-set : (Setof 'a)] [right-set : (Setof 'a)]): (Setof 'a)
  (foldl (lambda ([item : 'a] [set : (Setof 'a)]): (Setof 'a)
           (set-add set item))
         left-set
         (set->list right-set)))