guile-data-structures/trees/simple-binary-tree/unbalanced-set.scm

(library (unbalanced-set)
  (export make-empty-set
          set-insert
          set-empty?
          set-member?)
  (import (except (rnrs base) error vector-map)
          (only (guile)
                lambda*
                λ)
          ;; SRFI-9 for structs
          (srfi srfi-9 gnu)
          ;; let-values
          (srfi srfi-11)
          (ice-9 exceptions)
          (binary-tree))


  ;; Maybe it would be appropriate to wrap the unbalanced binary
  ;; search tree in a record, to have predicates and be able to store
  ;; the less operation.
  (define-immutable-record-type <unbalanced-set>
    (construct-empty-set items less)
    set?
    (items set-items set-set-items)
    (less set-less set-set-less))


  (define make-empty-set
    (λ (less)
      (construct-empty-set (make-empty-tree) less)))


  (define set-empty?
    (λ (set)
      (tree-empty? (set-items set))))


  (define set-member?
    (λ (set elem)
      (cond
       [(set-empty? set) #f]
       [else
        (tree-member? (set-items set)
                      elem
                      (set-less set))])))

  (define set-insert
    (λ (set elem)
      ;; note: copying the set struct here, which could be avoided by
      ;; not using a struct
      (set-set-items set
                     (tree-insert (set-items set)
                                  elem
                                  (set-less set))))))