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

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

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.

StackExchange Code Review Q#1803, answer score: 2