common-lisp Functions as first class values Implementing reverse and revappend


Example

Common Lisp already has a reverse function, but if it didn't, then it could be implemented easily using reduce. Given a list like

(1 2 3) === (cons 1 (cons 2 (cons 3 '())))

the reversed list is

(cons 3 (cons 2 (cons 1 '()))) === (3 2 1)

That may not be an obvious use of reduce, but if we have a "reversed cons" function, say xcons, such that

(xcons 1 2) === (2 . 1)

Then

(xcons (xcons (xcons () 1) 2) 3)

which is a reduction.

(reduce (lambda (x y)
          (cons y x))
        '(1 2 3 4)
        :initial-value '())
;=> (4 3 2 1)

Common Lisp has another useful function, revappend, which is a combination of reverse and append. Conceptually, it reverses a list and appends it to some tail:

(revappend '(3 2 1) '(4 5 6))
;;=> (1 2 3 4 5 6)

This can also be implemented with reduce. It fact, it's the same as the implementation of reverse above, except that the initial-value would need to be (4 5 6) instead of the empty list.

(reduce (lambda (x y)
          (cons y x))
        '(3 2 1)
        :initial-value '(4 5 6))
;=> (1 2 3 4 5 6)