;; Sid Stamm
;; C211 lab number 4: Cons & Recursion
;; 9-25-2003

;; Reminder: this can be found at http://www.cs.indiana.edu/~sstamm/c211/

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; CONS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Lists are made with cons cells that store two values.
;; Proper lists are made such that cons cells are linked
;; together: the first element in each cell is a value,
;; the second is a proper list.

;; This is what they look like:
; +--+--+  +--+--+
; |a | --->|b | ---> ()
; +--+--+  +--+--+
;
; This set of cons cells represents the list (a b)

;; Try out these examples:

(cons 'a (cons 'b '() ))
; (a b)

(cons (cons 'a (cons 'b '()))
      (cons (cons 'c (cons 'd '())) '() ))
; ((a b) (c d))

(cons 'a (cons (cons 'b 'c) '() ))
; (a (b . c))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Environments & Shadowing
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Try drawing the environments for each define and lambda
;; Then, trace where scheme finds y in each case.

(define x 2)
(define y 'jeff)
(define f (lambda (g y) (+ g y)))

(f 3 100) ;which y gets used?
; 103

(f x 100) ;Can you do this?
; 102

(f x y)   ;How about this?
; Error in +: jeff is not a number.

;; Lets try this again
(define f (lambda (g y) (+ g x y))) ;where will it find x?

(f 3 100)
;105

(f x 100)
;104

(f 1 100)
;103

(define x 1000)
(f 1 100) ;same thing again...
;1101

;;Why is this last number so big? We didn't redefine f...


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Recursion!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Example 1: Bean counter
(define bean-counter
  (lambda (ls)
    (if (null? ls)
	0
	(if (equal? (car ls) 'bean)
	    (+ 1 (bean-counter (cdr ls)))
	    (bean-counter (cdr ls))))))

(bean-counter '())
; 0

(bean-counter '(lima bean kidney bean bean man))
; 3

;; Or, in tail-recursive form
(define bc-tail
  (lambda (ls)
    (bc-helper ls 0)))
(define bc-helper
  (lambda (ls n)
    (if (null? ls)
	n
	(if (equal? (car ls) 'bean)
	    (bc-helper (cdr ls) (+ 1 n))
	    (bc-helper (cdr ls) n)))))

(bc-tail '())
; 0

(bc-tail '(lima bean kidney bean bean man))
; 3

;; Trace them individually
(trace bc-helper bean-counter bc-tail)

(bean-counter '(lima bean kidney bean bean man))
(bc-tail '(lima bean kidney bean bean man))

;; examine the difference
(untrace bc-helper bean-counter bc-tail)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; EXERCISES!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Yay!  It's your weekly brainstrain!

;; EXERCISE 1
;;----------------------------------------------------------
;; Define a procedure brewery that takes a single argument n
;; and returns a list containing n copies of the symbol beer.
;; Ex:
;;    > (brewery 4)
;;    (beer beer beer beer)
;;
;; You can use a helper or not, but explain why it is or why
;; it is not tail recursive.  (Provide evidence).
;; Think of more test cases for this problem.

;; Solution (nontail)
(define brewery
  (lambda (n)
    (if (< n 1)
	'()
	(cons 'beer (brewery (- n 1))))))

;; Solution (tail)
(define brewery-t
  (lambda (n)
    (brew-helper n '())))
(define brew-helper
  (lambda (n ls)
    (if (< n 1)
	ls
	(brew-helper (- n 1) (cons 'beer ls)))))


;; EXERCISE 2
;;----------------------------------------------------------
;; Define a procedure pest-control that takes one parameter
;; called bug-list and returns that same list but with all
;; occurances of the symbol bug removed.
;; Ex:
;;   >(pest-control '(roach bug fly moth bug pest))
;;   (roach fly moth pest)
;;
;; You can use a helper or not, but explain why it is or why
;; it is not tail recursive.  (Provide evidence).
;; Think of more test cases for this problem.

;; Solution (nontail)
(define pest-control
  (lambda (bug-list)
    (if (null? bug-list)
	'()
	(if (equal? (car bug-list) 'bug) ;is the car a bug?
	    (pest-control (cdr bug-list))
	    (cons (car bug-list) (pest-control (cdr bug-list)))))))

;; Solution (tail)
(define pest-control-t
  (lambda (bug-list)
    (reverse (p/c-helper bug-list '()))))
(define p/c-helper
  (lambda (b-list return-list)
    (if (null? b-list)
	return-list
	(if (equal? (car b-list) 'bug)
	    (p/c-helper (cdr b-list) return-list)
	    (p/c-helper (cdr b-list) (cons (car b-list) return-list))))))


;; EXERCISE 3
;;----------------------------------------------------------
;; This problem is a bit harder than the other two.
;; Define a procedure xerox that takes a parameter called
;; stuff that contains a string value and a number n.
;; Make it return a list containing n copies of the stuff.
;; Write this using tail-recursion.
;; Ex:
;;   >(xerox "report" 5)
;;   ("report" "report" "report" "report" "report")

;; Solution
(define xerox
  (lambda (stuff n)
    (xerox-machine stuff n '())))
(define xerox-machine
  (lambda (e n accum)
    (if (< n 1)
	accum
	(xerox-machine e (- n 1) (cons e accum)))))

;; Solution (nontail: cheap solution)
(define xerox-nt
  (lambda (stuff n)
    (if (< n 1)
	'()
	(cons stuff (xerox-nt stuff (- n 1))))))