; Das erlaubt es, constr-06.ss im ``Full Scheme''-level zu laden:
(define empty '()) 

(load "constr-06.ss")

;;; SIGNATUR
;;; btree-fold : (Y X Y -> Y) Y btree(X) -> Y
;;; ERKLÄRUNG
;;; (btree-fold c e t) "ersetzt" jedes Vorkommen von '() in t durch e
;;; und jedes Vorkommen von make-branch durch c und wertet den entstehenden
;;; Ausdruck aus.
;;; BEISPIEL
;;; (btree-fold * 1 '()) == 1
;;; (btree-fold * 1 (make-branch '() 2 (make-branch '() 3 '()))) == 6   
;;; (btree-fold (lambda (x y z) (append x (list y) z)) '()
;;;             (make-branch '() 2 (make-branch '() 3 '()))) == '(2 3) 
;;; (btree-fold (lambda (x y z) (+ x z 1)) 0
;;;             (make-branch '() 2 (make-branch '() 3 '()))) == 2 =^= btree-size
;;; DEFINITION:
(define btree-fold
  (lambda (c e t)
    (cond
     ((null? t)
      e)
     ((branch? t)
      (c (btree-fold c e (branch-left t))
         (branch-elem t)
         (btree-fold c e (branch-right t)))))))


;;; SIGNATUR
;;; btree-map: (X -> Y) btree(X) -> btree(Y)
;;; ERKLÄRUNG
;;; (btree-map c t) "ersetzt" jedes Element x in t durch (c x).
;;; BEISPIEL
;;; (btree-map - '()) == '()
;;; (btree-map - (make-branch '() 2 (make-branch '() 3 '())))
;;;    ==  (make-branch empty -2 (make-branch empty -3 empty))
;;; DEFINITION:
(define btree-map
  (lambda (c t)
    (btree-fold 
     (lambda (l e r) (make-branch l (c e) r))
     '()
     t)))


;;; SIGNATUR
;;; btree-flip : btree(X) -> btree(Y)
;;; ERKLÄRUNG
;;; (btree-fold c e t) vertauscht in jedem Knoten den linken mit dem
;;; rechten Teilbaum.
;;; BEISPIEL
;;; (btree-flip '()) == '()
;;; (btree-flip (make-branch '() 2 (make-branch '() 3 '())))
;;;    == (make-branch (make-branch empty 3 empty) 2 empty)
;;; DEFINITION:
(define btree-flip
  (lambda (t)
    (btree-fold
     (lambda (l e r) (make-branch r e l))
     '()
     t)))