I'm working my way through Structure and Interpretation of Computer Programs and got to exercises 2.27-2.28, reproduced here:
Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,
(define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4)) (reverse x) ((3 4) (1 2)) (deep-reverse x) ((4 3) (2 1))Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)
After solving them separately, it occurred to me one could write a single higher-order procedure to do both: a procedure that cdrs down the tree and appends to an accumulator another list obtained by applying some procedure to the head (depending on whether or not the head is itself a pair). We then postprocess that list in some way.
(define (tree-transform xs hd-is-pair hd-not-pair post-proc)
(define (iter items acc)
(cond ((null? items) acc)
((pair? (car items))
(iter (cdr items) (append acc (hd-is-pair (car items)))))
(else
(iter (cdr items) (append acc (hd-not-pair (car items)))))))
(post-proc (iter xs '())))
One can then define fringe and deep-reverse as follows (identity and reverse are already in my environment):
(define (fringe xs)
(tree-transform xs fringe list identity))
(define (deep-reverse xs)
(tree-transform xs (lambda(x) (list (deep-reverse x))) list reverse))
I'm still not entirely satisfied with this, so I'd like a review. In particular is there a place I should use let to label the car and cdr of items and make the overall structure clearer?
I'd also really appreciate advice on testing my Scheme code: how can I "step through" the execution of this code for a particular example? I'm aware there's a trace procedure but I'm looking for best practices.
appendin a recursive function is problematic; it can easily turn an otherwise linear time algorithm into a quadratic one. \$\endgroup\$reverseit when returning. Difference Lists are another possible approach I like - they build up a chain of closures via partial function application to get linear time appends when finalized. \$\endgroup\$