(module mp2 (lib "eopl.ss" "eopl")
 (provide  ;; omitting functions for Task 1 from public view
           bound-variables
           occurs-bound?
           binary-search-tree?
           occurs-within?
           ;; omitting functions for Task 6 from public view
           )

;;; Task 2
;;;
;;; bound-variables: LcExp -> Listof[Symbol]
;;;
;;; (bound-variables M) returns the identifiers that are bound
;;; by a lambda expression in M.

(define bound-variables
 (lambda (exp)
   (cond ((symbol? exp) '())
         ((eq? (car exp) 'lambda)
          (cons (car (cadr exp))
                (bound-variables (caddr exp))))
         (else
          (append (bound-variables (car exp))
                  (bound-variables (cadr exp)))))))

;;; Task 3
;;;
;;; occurs-bound?: Symbol * LcExp -> Bool
;;;
;;; (occurs-bound? x M) returns true iff x occurs bound in M

(define occurs-bound?
 (lambda (sym exp)
   (and (memq sym (bound-variables exp)) #t)))

;;; Task 4
;;;
;;; binary-search-tree?: Binary-search-tree -> Bool
;;;
;;; (binary-search-tree? b) returns true iff b satisfies the
;;; context-sensitive representation invariant on page 10 of
;;; the textbook.

(define binary-search-tree?
 (lambda (b)
   (cond ((null? b) #t)
         (else
          (let ((label (car b))
                (left  (cadr b))
                (right (caddr b)))
            (and (binary-search-tree? left)
                 (binary-search-tree? right)
                 (binary-search-tree-help left <= label)
                 (binary-search-tree-help right > label)))))))

;;; binary-search-tree-help:
;;;     Binary-search-tree * (Integer * Integer -> Bool) * Integer -> Bool
;;;
;;; (binary-search-tree-help b p? n) returns truee iff every label m in b
;;; satisfies (p? m n).

(define binary-search-tree-help
 (lambda (b p? n)
   (cond ((null? b) #t)
         (else
          (let ((label (car b))
                (left  (cadr b))
                (right (caddr b)))
            (and (p? label n)
                 (binary-search-tree-help left p? n)
                 (binary-search-tree-help right p? n)))))))

;;; Task 5
;;;
;;; occurs-within?: Integer * Binary-search-tree -> Bool
;;;
;;; (occurs-within? m bst) returns true iff m occurs as a label within b,
;;; which is assumed to satisfy the binary-search-tree? predicate.

(define occurs-within?
 (lambda (m bst)
   (cond ((null? bst) #f)
         (else
          (let ((label (car bst))
                (left  (cadr bst))
                (right (caddr bst)))
            (cond ((< m label)
                   (occurs-within? m left))
                  ((> m label)
                   (occurs-within? m right))
                  (else #t)))))))
)