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

(library (unbalanced-map)
  (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-map>
    (construct-empty-set items less)
    map?
    (items map-items set-map-items)
    (less map-less set-map-less))


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


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


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

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