# Reverse in terms of fold-right and fold-left

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))


(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))


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.

• 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. – 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.