2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Unless the first list is known to be short, using append in a recursive function is problematic; it can easily turn an otherwise linear time algorithm into a quadratic one. \$\endgroup\$ Commented Mar 4 at 22:53
  • \$\begingroup\$ @Shawn Interesting! Looking around online I can see that advice given for other languages. How do I avoid this? I know Scheme has tail-recursion to handle scenarios like this, how can I use it here? \$\endgroup\$ Commented Mar 5 at 1:52
  • \$\begingroup\$ Tail recursion instead is always an option; build the list in reverse order in an accumulator variable and then reverse it 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\$ Commented Mar 5 at 22:06

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.