Quote:
Original post by GameDev Doctor
Time to get feedback on 3.17 to 3.19, and confirm that my answer to 3.19 is indeed in constant space.
*** Source Snippet Removed ***
The implementation of count-pairs is a bit wierd, with the lambda at the end, but I had trouble making items reset in subsequent calls.
Exercise 3.17
You can write your count-pairs like this if you want to get rid of the weird lambda at the end.
(define (count-pairs x) (let ((items '())) (define (count x) (if (or (not (pair? x)) (initems? x items)) 0 (begin (set! items (cons x items)) (+ 1 (count (car x)) (count (cdr x)))))) (set! items '()) (count x)))A define can hold multiple expressions, as can a lambda, thus no need for begin there. Also, don't be afraid to use multiple lines.
I must admit I don't like this solution very much. It's half imperative, half not-tail-recursive functional. Try to make it fully functional and tail recursive.
Another important aspect about functional programming is recognizing patterns in your code. Now, in that specific exercise, no patterns occur. But if you take all exercises you've made so far, you must have noticed that a general (some? pred lst) function, taking a predicate and checking if any element in lst makes it return #t, might come in handy. Otherwise you'll end writing the same kind of conds over and over again. See my other thread (titled Map, Reduce and Co. IIRC) for more such helper functions.
(define (some? pred lst) (and (not (null? lst)) (or (pred (car lst)) (some? pred (cdr lst)))))(define (member? item lst) (some? (lambda (x) (eq? x item)) lst))(define (count-pairs lst) (define (count-pairs todo done acc) (if (null? todo) acc (let ((current (car todo)) (rest (cdr todo))) (if (or (not (pair? current)) (member? current done)) (count-pairs rest done acc) (count-pairs (append (list (car current) (cdr current)) (cdr todo)) (cons current done) (+ acc 1)))))) (count-pairs (list lst) () 0))
