Reverse in terms of fold-right and fold-left

Question

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) 
 initial
 (op (car rest)
 (rec (cdr rest)))))
 (rec seq))
(define (fold-left op initial seq)
 (define (iter result rest)
 (if (null? rest)
 result
 (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))

Answer 1

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.

• jaresty: 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.

Answer 2

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.