oh-9-27.rkt

#lang racket

;; CIS352 Office hours code -- 9/27/2023
;; matching and type predicates

;; Direct-style length
(define (length lst)
  (if (empty? lst)
      0
      (add1 (length (rest lst)))))

(define (list? d)
  (if (equal? d '())
      #t
      (and (cons? d) (list? (rest d)))))

;; using matching
(define (length-again lst)
  (match lst
    ['() 0]
    [(cons hd tl)
     ;; within the body of the match, hd and tl are bound
     ;; in the previous function, I had to use (rest lst)
     ;; to get tl, rather than matching
     (add1 (length-again tl))]))

;; using match
(define (fib n)
  (match n
    [0 1]
    [1 1]
    [_ (+ (fib (- n 1)) (fib (- n 2)))]))

;; if we hadn't used match, we'd have to use cond or something similar
#;(define (fib n)
  (cond
    [(= n 0) 1]
    [(= n 1) 1]
    [else (+ (fib (- n 1)) (fib (- n 2)))]))

;; matching can be used to extract pieces from complex structured
;; expressions (S-expressions)
(match '(if (= 4 4) 2 3) ; '(if (= 3 (+ 1 2)) "hello" "goodbye")
  [`(if (= ,e0 ,e1) ,e-true ,e-false)
   (pretty-print e0)
   (pretty-print e1)
   (if (= e0 e1) e-true e-false)])

;; A "type predicate" that characterizes the shape of trees
;; any recursive function you write that recurs over the structure
;; of trees, should roughly follow this template
(define (tree? t)
  (match t
    ['empty #t]
    [`(node ,n ,(? tree? t0) ,(? tree? t1)) #t]
    [_ #f]))

;; some recursive functions on trees

;; calculate the maximum value in t
;; assume t satisfies (i.e., returns #t for) tree? above
(define (tree-max t)
  (match t
    ['empty -inf.0]
    [`(node ,n ,t0 ,t1)
     (max n (tree-max t0) (tree-max t1))]))

(tree-max '(node 5 (node 15 empty empty) (node 20 (node 12 empty empty) empty)))

;; A tree's height is either 0 for the empty tree or 1+the maximum of its two children
(define (tree-height t)
  (match t
    ['empty 0]
    [`(node ,_ ,t0 ,t1) (add1 (max (tree-height t0) (tree-height t1)))]))

;; A tree is balanced when no subtree differs in depth > 1 from the other
(define (tree-balanced? t)
  (match t
    ['empty #t]
    [`(node ,_ ,t0 ,t1) (<= (abs (- (tree-height t0) (tree-height t1))) 1)]))

(tree-height '(node 5 (node 15 empty empty) (node 20 (node 12 empty empty) empty)))
(tree-balanced? '(node 5 (node 15 empty empty) (node 20 (node 12 (node 10 empty empty) empty) empty)))