Exercise 2.39

Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38:

(define (reverse sequence)
  (fold-right (lambda (x y) <??>) nil sequence))
(define (reverse sequence)
  (fold-left (lambda (x y) <??>) nil sequence))

I wrote this answer:

(define (fold-right op initial seq)
  (define (rec rest)
    (if (null? rest) 
        (op (car rest)
            (rec (cdr rest)))))
  (rec seq))

(define (fold-left op initial seq)
  (define (iter result rest)
    (if (null? rest)
        (iter (op result (car rest)) (cdr rest))))
  (iter initial seq))

(define (reverse sequence)
  (fold-right (lambda (x y) 
                (append  y (list x))) null sequence))

(define (reverse-l sequence)
  (fold-left (lambda (x y) (cons y x)) null sequence))

(define a (list 1 2 3 4 5))

Your implementation of reverse using fold-left is correct.

In the case of reverse using fold-right, you may use snoc (described below) in place of append. It looks better and its complexity is no worse than that of append, so there is no loss in efficiency:

(define (snoc e lis)
  (if (null? lis)
      (cons e lis)
      (cons (car lis) (snoc e (cdr lis)))))

(define (reverse sequence)
  (fold-right (lambda (x y)
                (snoc x y)) null sequence))

... or even more succinct:

(define (reverse sequence)
  (fold-right snoc null sequence))

It is curious that SICP's definition of fold-left swaps arguments to op (but retains the correct ordering of arguments to op in fold-right), resulting in the use of a rather tedious (lambda (x y) (cons y x)) instead of a simple cons. SRFI-1 gets the definitions of fold and fold-right correct, of course.

  • \$\begingroup\$ Thanks! I was surprised that you didn't have to snoc in reverse order for fold-right, but I tested it and it works. Interesting. \$\endgroup\$
    – jaresty
    Apr 13 '11 at 6:13

Yep, youve got it. I don't think there are any reasonable alternatives.

It's umderstandable if you were hoping to avoid append with some clever combo of cons/car/cdr but i dont believe there is such a way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.