Section 7.9 of David Touretzky’s Gentle Introduction to Common Lisp (Download) introduces the reduce operator. Given two inputs, a function and a list, this applicative operator reduces the elements of the input list to a single result value. reduce might be seen as a variant of apply. It’s very intuitive. See this Lisp example:
|
1 2 3 4 |
CL-USER> (reduce #'+ '(1 2 3)) 6 CL-USER> (reduce #'append '((one un) (two deux) (three trois))) (ONE UN TWO DEUX THREE TROIS) |
and the same in Clojure:
|
1 2 3 4 |
user> (reduce + '(1 2 3)) 6 user> (reduce into '((one un) (two deux) (three trois))) (trois three deux two one un) |
There is no direct equivalent for append in Clojure. There is a function conj, but applying it to the input list (here: a list of lists) doesn’t produce the output that we want:
|
1 2 |
user> (reduce conj '((one un) (two deux) (three trois))) ((three trois) (two deux) one un) |
The into function creates a new collection by conjoining all elements of the input collection:
|
1 2 |
user> (into () '((one un) (two deux) (three trois))) ((three trois) (two deux) (one un)) |
But as you can see, this isn’t enough. With reduce the respective elements of the input collection are ‘melted’ into a single collection. (This collection might be a list, a vector, or whatever.) But we are running off the track.
Exercise 7.16 makes us write a function that collapses a list of sets into a single set. Note that a set is defined by the uniqueness of its members, so no element must appear more than once in the result set.
Exercise 7.17 asks for a function with a list of lists as input that calculates the total length of this list.
This is the Lisp code for exercises 7.16 and 7.17:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
;;; ex 7.16 ;;; call with (append-to-set '((a b c) (c d a) (f b d) (g))) (defun append-to-set (x) "unify x, a list of sets and make it a new set" (remove-duplicates (reduce #'append x))) ;;; ex 7.17 ;; total length of a list of lists: many conses (defun lenlist (x) (length (reduce #'append x))) ;; less conses (defun lenlist2 (x) (reduce #'+ (mapcar #'length x))) |
And this is the same code written in Clojure:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
;;; ex 7.16 (defn append-to-set [x] (distinct (reduce into x))) ;;; ex 7.17 (defn lenlist [x] ;; call (lenlist '((a b c) (c d a) (f b d) (g))) (count (reduce into x))) (defn lenlist2 [x] (reduce + (map count x))) |
Omitting duplicates in Lisp is done by calling remove-duplicates. Clojure’s distinct does the same thing. The original sets that were appended (Lisp) or into’d lose their duplicates this way, a very concise solution. There are two different solutions for exercise 7.17, respectively. Both are correct, but the second one results in better performance, at least in Lisp, because each append in the first solution creates cons actions that consume a lot of memory. I’m not sure if this is still true for the Clojure versions, but I’m giving you both solutions, anyway.
Exercise 7.18 wants to know why (reduce #’+ nil) returns 0 and (reduce #’* nil) returns 1. For answering this, we need a bit of math. Given two lists x and y, then
|
1 |
(reduce #'+ (append x y)) |
should be equivalent to
|
1 |
(+ (reduce #'+ x) (reduce #'+ y)) |
– that is the sum of the sums of x and y, respectively. If y is NIL, then (append x y) evaluates to x; so (reduce #’+ y) must result in 0. This makes 0 the identity value for addition, and this is the reason why calling ‘+’ with no arguments results in 0. 1 is the identity value for multiplication, so calling ‘*’ with no arguments results in 1.
Here you can see it the Lisp way:
|
1 2 |
CL-USER> (reduce #'+ nil) 0 |
And so it’s called in Clojure:
|
1 2 |
user> (reduce + '()) 0 |
