;; my-reverse : [Listof X] -> [Listof X] ;; reverse the order of the list (define (my-reverse.slow lox) (cond [(empty? lox) empty] [(cons? lox) (append (my-reverse.slow (rest lox)) (list (first lox)))])) ;; reverse-onto : [Listof X] [Listof X] -> [Listof X] ;; reverse lox and append it to the front of ans (define (reverse-onto lox ans) (cond [(empty? lox) ans] [(cons? lox) (reverse-onto (rest lox) (cons (first lox) ans))])) (check-expect (reverse-onto '() '()) '()) (check-expect (reverse-onto '() '(x y z)) '(x y z)) (check-expect (reverse-onto '(a b c) '()) '(c b a)) (check-expect (reverse-onto '(a b c) '(x y z)) '(c b a x y z)) (define (my-reverse lox) (reverse-onto lox '())) (check-expect (my-reverse '()) '()) (check-expect (my-reverse '(1 2 3)) '(3 2 1)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; my-foldl : [X Y -> Y] Y [Listof X] -> Y ;; base serves as accumulator; represents answer so far ;; Idea: (foldl f base (cons x xs)) = (foldl f (f x base) xs) (define (my-foldl f base lox) (cond [(empty? lox) base] [(cons? lox) (my-foldl f (f (first lox) base) (rest lox)) ])) (check-expect (my-foldl cons empty '(a b c d e)) '(e d c b a)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; fact : Natural -> Natural ;; compute factorial of n (i.e., n * (n-1)* ... * 1) #;(define (fact n) (cond [(zero? n) 1] [else (* n (fact (sub1 n)))])) ;;-------------------------- ;; Accumulator-based design: ;; fact : Natural -> Natural ;; compute factorial of n (i.e., n * (n-1)* ... * 1) (define (fact n) (local (;; Natural Natural -> Natural ;; compute n! * acc (define (fact-accum n acc) (cond [(zero? n) acc] [else (fact-accum (sub1 n) (* n acc))]))) (fact-accum n 1))) (check-expect (fact 0) 1) (check-expect (fact 5) 120) #| -- ACCUMULATORS are orthogonal to structural design or generative recursion design. -- Why/when use it? The function somehow doesn't have enough information for the recursive cases to do its job well or efficiently: reverse, path? Symptom 1: you need to re-process the result for structural recursions Symptom 2: your function can't find the solution even though there is one Symptom 3: you want to process things in a different order than the natural one -- Design needs a change to the structural/generative template: Question 1: what information do you need to keep track of? Add a parameter and its signature Question 2: what's the "starting information"? Remember it. Question 3: when your function recurs it "drops" information. How do you add it (accumulate it) to the existing accumulator parameter? ... (selector main-argument) ... accumulator ... cons, +, ... etc. Question 4: how do you use the accumulated information in the function? New base case? Result of base case? The answer to this question may give you a hint for Questions 2/3. DONE: when wrapped up in local and initialized with Starting Information |#