#lang racket

; Signature: make-tree(1st, ..., nth)
; Type: [Tree * ... * Tree -> Tree]
(define make-tree list)
; Signature: add-subtree(subtree, tree)
; Type: [Tree * Tree -> Tree]
(define add-subtree cons)
; Signature: make-leaf(data)
; Type: [T -> Tree]
(define make-leaf (lambda (d) d))
; Signature: empty-tree
; Type: Empty-Tree
(define empty-tree empty)
; Signature: first-subtree(tree)
; Type: [Tree -> Tree]
(define first-subtree car)
; Signature: rest-subtrees(tree)
; Type: [Tree -> Tree]
(define rest-subtrees cdr)
; Signature: leaf-data(leaf)
; Type: [Tree -> T]
(define leaf-data (lambda (x) x))
; Signature: composite-tree?(e)
; Type: [T -> Boolean]
(define composite-tree? pair?)
; Signature: leaf?(e)
; Type: [T -> Boolean]
(define leaf? (lambda (t) (not (list? t))))
; Signature: empty-tree?(e)
; Type: [T -> Boolean]
(define empty-tree? empty?)

;; The empty lazy list value (a singleton datatype)
(define empty-lzl '())

;; Purpose: Value constructor for non-empty lazy-list values
;; Type: [T * [Empty -> LZL(T)] -> LZT(T)]
(define cons-lzl cons)

;; Accessors
;; Type: [LZL(T) -> T]
;; Precondition: Input is non-empty
(define head car)

;; Type: [LZL(T) -> LZL(T)]
;; Precondition: Input is non-empty
;; Note that this *executes* the continuation
(define tail
  (lambda (lzl)
  ((cdr lzl))))

;; Type predicate
(define empty-lzl? empty?)

;; Signature: take(lz-lst,n)
;; Type: [LzL*Number -> List]
;; If n > length(lz-lst) then the result is lz-lst as a List
(define take
  (lambda (lz-lst n)
    (if (or (= n 0) (empty-lzl? lz-lst))
      empty-lzl
      (cons (head lz-lst)
            (take (tail lz-lst) (- n 1))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;            start            ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; Signature: tree->leaves(tree : Tree)
; Type: [Tree -> List(Any)]
; Purpose: Returns an ordered list of the labels which appear in the leaves of the tree.
; Precondition: tree is of type Tree.
; Test: (tree->leaves '(a (b c)(((x y))))) => '(a b c x y)
(define tree->leaves
  (lambda (tree)
    (if (empty-tree? tree) '()
        (if (leaf? tree) (list tree)
            (append (tree->leaves (first-subtree tree)) (tree->leaves (rest-subtrees tree)))
        )
    )
 ))

; Signature: list-to-lzlist(lst : List)
; Type: [List(Any) -> LZL]
; Purpose: Returns a lazy list of a list
; Precondition: lst is a list
; Test: (take (list-to-lzlist '(1 2 3)) 2) => '(1 2)
(define list-to-lzlist
  (lambda (lst)
    (cons-lzl (car lst)
              (lambda ()
                (if (empty? (cdr lst))
                    empty-lzl
                    (list-to-lzlist (cdr lst))
                )
    )
)))

; Signature: tree->lz-leaves(tree : Tree)
; Type: [Tree -> LZL]
; Purpose: Returns an ordered lazy list of the labels which appear in the leaves of the tree.
; Precondition: tree is of type Tree
; Test: (take (tree->lz-leaves '(a (b c)(((x y))))) 5) => '(a b c x y)
(define tree->lz-leaves
  (lambda (tree)
    (list-to-lzlist (tree->leaves tree))
))

; Signature: lzlists-equal?(lzl1 : LZL, lzl2 : LZL)
; Type: [LZL * LZL -> Boolean | Pair]
; Purpose: Returns #t if the lazy lists are equal, otherwise returns a pair of the first unequal elements.
; Precondition: lzl1, lzl2 are lazy lists.
; Tests: (lzlists-equal? (list-to-lzlist '(1 2 3)) (list-to-lzlist '(1 2 3))) => #t
;        (lzlists-equal? (list-to-lzlist '(1 5 3)) (list-to-lzlist '(1 2 3))) => '(5 . 2)
(define lzlists-equal?
  (lambda (lzl1 lzl2)
    (if (and (empty-lzl? lzl1) (empty-lzl? lzl2))
        #t
        (if (or (empty-lzl? lzl1) (empty-lzl? lzl2))
            (if (empty-lzl? lzl1)
                (cons empty (head lzl2))
                (cons (head lzl1) empty)
            )
        (if (not (equal? (head lzl1) (head lzl2)))
            (cons (head lzl1) (head lzl2))
            (lzlists-equal? (tail lzl1) (tail lzl2))
        )
        )
)))

; Signature: same-leaves?(t1 : Tree, t1 : Tree)
; Type: [Tree * Tree -> Boolean | Pair]
; Purpose: Returns #t if the trees have the same leaves (ordered),
;          otherwise returns a pair of the first unequal leaves.
; Precondition: t1, t2 are of type Tree.
; Tests: (same-leaves? '((a b) c) '(a (b c))); => #t
;        (same-leaves? '(a (b c)) '(a d c)); => '(b . d)
(define same-leaves?
  (lambda (t1 t2)
    (lzlists-equal? (tree->lz-leaves t1) (tree->lz-leaves t2))
))