#lang lsl

;; We'll define a tree where each node has a key, value, and two descendents.
(define-struct leaf [])
(define-struct node [k v l r])
(define-contract (Tree K V)
  (OneOf (Struct leaf [])
         (Struct node [K V (Tree K V) (Tree K V)])))

;; The operations that a set should support
(define-struct sop [empty singleton union intersect member?])
(define-contract (Sop Set Elt)
  (Struct sop [Set
               (-> Elt Set)
               (-> Set Set Set)
               (-> Set Set Set)
               (-> Elt Set Boolean)]))

(: tree-keys (All (Set V)
                  (-> (Sop Set String)
                      (Tree String V)
                      Set)))

;; Exercise 1: Implementing sets as lists

(define SOP-LIST ...)

;; Exercise 2: Writing a test

(define T1 ...)
(define T1-KEYS (list ...))

(define (t1-prop sop) ...)

;; Exercise 3: Implementing tree-keys, using the set interface

(define (tree-keys sop t)
   ...)

(check-satisfied SOP-LIST t1-prop)

;; Exercise 4: Implementing sets as characteristic functions

(define SOP-FUN ...)

(check-satisfied SOP-FUN t1-prop)

;; Challenge: If you finished early, come up with a third implementation - maybe a tree?