Lecture 12
Feb 13

(define (filter-c pred) ... ???)

so that
((filter-c odd?) '(1 2 3 4 5 6 7 8 9 10)) => (1 3 5 7 9)

(define (filter-c pred)
	(flat-recurse '() (lambda (x y)
			(..................

----------------------------------------------------------------------------

(define sum-all
	(letrec ((helper
		(lambda (ls)
			(if (null? ls)
				0
				(let ([a (car ls)])
					(if (or (pair? a) (null? a))
						(+ (helper a) (helper (cdr ls)))
						(+ a (helper (cdr ls)))))))])
	helper))

(define (filter-all-c pred)
	(letrec ([helper
		(lambda (ls)
			(if (null? ls)
				'()
				(let ([a (car ls)])
					(if (or (pair? a) (null? a))
						(cons (helper..........................................

----------------------------------------------------------------------------

assoc & memoizing

memoizing: store values of lengthy computations in a table and when proc is
called, check first if the value is already in the table; if not, store it there...

table: ( (arg1 . (proc arg1)) ... (argn . (proc argn)) )  (dotted pair needs 1 cons instead of 2, and 2.
element is cdr instead of cadr...)

(a . b)
(a b)
    ^--- cadr

(define (lookup obj table success-contin failure-contin)
	(letrec ((lookup (lambda (table)	;; bec. other params don't chance
		(if (null? table)
			(failure-contin)
			(let ((pair (car table)))
				(if (equal? (car pair) obj)
					(success-contin pair)
					(lookup (cdr table))))))))
	(lookup table))))

(define (assoc obj table)	;; behaves like built in version, slower...
	(lookup obj table (lambda (pr) pr) (lambda () #f)))

(assoc 4 '((1 1 1) (2 4 4) (4 16 64) ...) =>  (4 16 64)

----------------------------------------------------------------------------

memoizing

(define (memoize proc)
	(let ((table '()))
		(lambda (arg)
			(lookup arg table
				(lambda (pr (cdr pr))	;; or just cdr ;~)
				(lambda()
					(let ((val (proc arg)))
						(set! table (cons (cons arg val) table))
						val)))))))

memoizing is fast

----------------------------------------------------------------------------

set-car! and set-cdr! mutate lists

(define (append x y) ;; leaves x and y unchanged
	(if (null? x)
		y
		(cons (car x) (append (cdr x) y))))

----------------------------------------------------------------------------

omg, what does it do???

(define (what x)
	(define (loop x y)
		(if (null? x)
			y
			(let ((temp (cdr x)))
				(set-cdr! x y)
				(loop tempx))))
	(loop x '()))

(what '(a b c)) ==> '(c b a)
reverses the list

btw, set-car! and set-cdr! can be fined in terms of set!:
assignment is all we ever need to get into trouble :-))))))))))))))))))))))

----------------------------------------------------------------------------

queues

(define (make-queue) (cons '() '()))

(define (empty-queue? q)
	(null? (front-ptr q))) where
(front-ptr q) is (car q)...

(define (front-queue q)
	(if (empty-queue? q)
		(error "....")
		(car (front-ptr q)))))

(define (enqueue! q item)
	(let ((new-pair (cons item '()))))
		(cond ((empty-queue? q) (set-front-ptr! q new-pair)	;; i.e. set-car!
				         (set-rear-ptr! q new-pair) q)	;; i.e. set-cdr!
		          (else (set-cdr! (rear-ptr q) new-pair)
			(set-rear-ptr! q new-pair) q)))))

(define (dequeue! q)
	(cond ((empty-queue? q) (error "..."))
		(else (set-front-ptr! q (cdr (front-ptr q)))
			q)))

----------------------------------------------------------------------------

HEAVY ON FINAL:
counters, withdraw procedures (i.e. new-withdraw, withdraw1, make-withdraw)

(define (make-withdraw balance)
	(lambda (amount)
		(if (>= balance amount)
			(begin (set! balance (~ balance amount))
				balance)
		"Insufficient funds")))

(define (withdraw amount)
	(if (>= balance amount)
		(begin (set! balance (- balance amount))
			balance)
		"Insufficient funds"))))

(define (dispatch m)
	(cond	((eq? m 'withdraw) withdraw)
		((eq? m 'deposit) deposit)
		(else (error "Unknown request -- MAKE-ACCOUNT"
			m))))
dispatch)

(define acc (make-account 100))
((acc'withdraw) 50)
((acc 'withdraw) 20)

----------------------------------------------------------------------------

Midterm Exam

1 short multiple choice
- know the concepts
- rewrite expression to fix the code

long answer
to write a procedure etc

everything excluding environment model and before the currying

answer randomly
---
what is the output
short problems (photo taken as example) (this example is hard problem)
   - transform leaves of the tree of numbers into trees of same structure
     but with all negative numbers replaced by 0
         - check to see if theres list
         - take the car; if not a pair check if it negative and cons on to cdr recursion.
         - if it list, apply recursion on the whole thing\

(define (replace-negatives tree)
	(if (null? tree)
		'()
		(cons (cond ((pair? (car tree)) (replace-negatives (car tree)))
			    ((negative? (car tree)) 0)
			    (else (car tree)))
		(replace-negatives (cdr tree)))))

DO NOT USE SET!