Lisp’s every operator takes a predicate and a list as input. If there is no element inhibiting the predicate, then the answer is true. Some samples in Lisp:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
CL-USER> (every #'numberp '(1 2 3 4 5)) T CL-USER> (every #'numberp '(1 2 3 4 5 A)) NIL CL-USER> (every #'(lambda (x) (> x 0)) '(1 2 3 4 5)) T CL-USER> (every #'(lambda (x) (> x 0)) '(1 2 3 4 5 -6)) NIL CL-USER> (every #'oddp nil) T CL-USER> (every #'evenp nil) T CL-USER> (every #'> '(10 20 30 40) '(1 5 11 23)) T |
The last one is especially interesting since Lisp’s every is able to operate on multiple lists, too. This is a bit different with Clojure. Here are Clojure’s appropriate expressions:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
user> (every? number? '(1 2 3 4 5)) true user> (every? number? '(1 2 3 4 5 A)) false user> (every? #(> % 0) '(1 2 3 4 5)) true user> (every? #(> % 0) '(1 2 3 4 5 -6)) false user> (every? odd? nil) true user> (every? odd? '()) true user> (every? even? nil) true user> (every? even? '()) true user> (map #(> %1 %2) '(10 20 30 40) '(1 5 11 23)) (true true true true) user> (every? true? (map #(> %1 %2) '(10 20 30 40) '(1 5 11 23))) true |
The first three expressions are very similar to their Lisp equivalents. In Clojure nil and the empty list / sequence are something different, that’s why (every? odd? …) and (every? even? …) yielding the same results is remarkable. Clojure’s every only allows two arguments, so we have to map the comparison in the last example before we are checking for the truth of all mappings. The result is the same.
The exercises 7.19 to 7.22 are asking for writing various functions:
- ALL-ODD (exercise 7.19): return t / true if all elements in a list of numbers are odd,
- NONE-ODD (exercise 7.20): return t / true if all elements in a list of numbers are not odd (that means: all have to be even),
- NOT-ALL-ODD (exercise 7.21): return t / true if there is at least one even element in a list of numbers,
- NOT-NONE-ODD (exercise 7.21): return t / true if there is at least one odd element in a list of numbers.
That’s the Lisp code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
;;; ex 7.19 (defun all-odd (x) (every #'oddp x)) ;;; ex 7.20 (defun none-odd (x) (every #'evenp x)) ;;; ex 7.21 (defun not-all-odd (x) (find-if #'evenp x)) ;;; ex 7.22 (defun not-one-odd (x) (if (find-if #'oddp x) t)) |
And this is the same in Clojure:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
;;; ex 7.19 (defn all-odd [x] (every? odd? x)) ;;; ex 7.20 (defn none-odd [x] (every? even? x)) ;;; ex 7.21 (defn not-all-odd [x] (some even? x)) ;;; ex 7.21 (defn not-all-odd2 [x] (first (filter even? x))) ;;; Ex 7.22 (defn not-none-odd [x] (if (some odd? x) true false)) |
We should take a look on not-all-odd in both dialects. find-if in Lisp returns the first even number (if found), while some in Clojure only returns true or false. Emulating find-if’s behaviour in Clojure is best done using the filter function (see part three) which does the same, but for all even numbers found by it. If we want just the first one, just use first.
Let’s skip the other exercises that run through redefining filters from A to Z and continue with something more interesting. Chapter 7’s keyboard exercise picks up a famous problem of Artificial Intelligence (I remember a Scientific American article from the early 1980s when I first read about it.) It’s ‘Block’s World’ and deals with various operations on a simple ‘world’ consisting of shapes of different size, material, and colours, and their appropriate position. I won’t repeat the various definitions of exercise 7.29; you can find them in David Touretzky’s Gentle Introduction to Common Lisp (which is freely available for download).
This is the Lisp code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
;;; ex 7.29 ;;; block's world (defparameter database '((b1 shape brick) (b1 color green) (b1 size small) (b1 supported-by b2) (b1 supported-by b3) (b2 shape brick) (b2 color red) (b2 size small) (b2 supports b1) (b2 left-of b3) (b3 shape brick) (b3 color red) (b3 size small) (b3 supports b1) (b3 right-of b2) (b4 shape pyramid) (b4 color blue) (b4 size large) (b4 supported-by b5) (b5 shape cube) (b5 color green) (b5 size large) (b5 supports b4) (b6 shape brick) (b6 color purple) (b6 size large))) ;;; a (defun match-element (s1 s2) "Match two symbols, return t if s1 and s2 match." (or (eq s1 s2) (eq s2 '?))) ;;; b (defun match-triple (assertion pattern) "Return t if assertion matches pattern." (every #'(lambda (s) (equal t s)) (mapcar #'match-element assertion pattern))) ;; better: (defun _match-triple (assertion pattern) "Return t if assertion matches pattern." (every #'match-element assertion pattern)) ;;; c (defun fetch (pattern) "Find records in database that match pattern." (remove-if-not #'(lambda (x) (match-triple x pattern)) database)) ;;; e (defun whatcolor-pattern (block) "Return a pattern asking for the color of block x." (list block 'color '?)) ;;; f (defun supporters (x) "Return the list of blocks that support x." (let ((fetchlist (list '? 'supports x))) (mapcar #'first (fetch fetchlist)))) ;;; or: (defun _supporters (block) (mapcar #'caddr (fetch (list block 'supported-by '?)))) ;;; g (defun supp-cube (x) "Return t if x is supported by a cube." (let ((supported-objects (supporters x))) ;; now we have a list of blocks supporting x, e.g. (b2 b3) ;; test if the members of this list are cubes (if (remove-if-not #'(lambda (x) (fetch (list x 'shape 'cube))) supported-objects) t))) ;;; h (defun desc1 (block) "Return all assertions belonging to x" (fetch (list block '? '?))) ;;; i (defun desc2 (block) "Call desc1, strip block name from results" (mapcar #'rest (desc1 block))) ;;; j (defun _description (block) "Flatten the output of desc2" (reduce #'append (desc2 block))) |
…and this is the same in Clojure:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
;;; ex 7.29 ;;; block's world (def database '[{ :block b1 :shape brick :color green :size small :supported-by (b2 b3) } { :block b2 :shape brick :color red :size small :supports b1 :left-of b3 } { :block b3 :shape brick :color red :size small :supports b1 :right-of b2 } { :block b4 :shape pyramid :color blue :size large :supported-by b5 } { :block b5 :shape cube :color green :size large :supports b4 } { :block b6 :shape brick :color purple :size large }]) ;;; a (defn match-element [s1 s2] (or (= s1 s2) (= s2 '?))) ;;; b (defn match-triple [assertion-map pattern-map] ;; call: (match-triple '{ :block b1 :color green :size small } '{:block ? :size ? :color ?}) => true (let [filter-keys (keys pattern-map)] (every? true? (vals (select-keys (merge-with match-element assertion-map pattern-map) (into [] filter-keys)))))) ;;; c ;;; call: (fetch '{ :shape brick }) (defn fetch [pattern] (filter (fn [x] (match-triple x pattern)) database)) ;;; d ;;; (fetch '{ :block b4 :shape ? }) ;;; (fetch '{ :shape brick }) ;;; (fetch '{ :block b2 :supports ?}) ;;; (fetch '{ :block b3 :supports ?}) ;;; (fetch '{ :color ?}) ;;; (fetch '{ :block b4 }) ;;; e (defn what-pattern [pattern property] `{ ~(keyword pattern) ~property } ) ;;; f (defn supporters [block] (distinct (flatten (conj (map #(get % :block) (fetch {:supports block})) (map #(get % :supported-by) (fetch {:block block :supported-by '?})))))) ;;; g (defn supp-cube "Return true if x is supported by a cube." [x] (= (map #(get % :block) (fetch {:shape 'cube})) (supporters x))) ;;; h, i, j ;;; omitted, a call like (fetch {:block 'b1}) will do ;;; l ;;; add a :material key |
There are some serious differences compared to the Lisp code. While the ‘database’ in the Lisp code is basically a list of lists, we have defined it as a map in the Clojure code. This results in a data structure that is much more a ‘database’ than a list of lists is: the keys are given by name, shape, colour, size, support and location information. This structure makes accessing each element very simple, as we can see in the code.
Both match-element functions are nearly identical. match-triple, however, deserves a bit more attention. Due to the changed structure of ‘database’ we have to regard the inequality of keys in the assertion- and pattern map. I.e., a call like (merge-with match-element '{ :block b1 :color green :shape brick } '{:block ? :color ?}) results in {:block true, :color true, :shape brick} – which would be false due to the unneeded ‘brick’ key. We solve this by limiting the comparison to only these key/value pairs that appear in both maps. We do this by calling select-keys with the pattern-map’s keys as a filter. Thus the call (select-keys (merge-with match-element '{ :block b1 :color green :shape brick } '{:block ? :color ?}) [:block :color]) takes only the pattern’s keys for comparison and results in {:color true, :block true} – which is exactly what we want.
fetch is very similar in both dialects despite the fact that we are using very different data structures in each language. While the Lisp fetch expects a call like (fetch '(b2 color ?)) the appropriate Clojure call is (fetch '{:block b2 :color ?}). And while exercise e just asks for a function that returns a block / colour pattern, the Clojure construct is a universal one, because the map structure makes it so remarkably easy. It just returns a map with the pattern as key (color, for example) and its corresponding attribute, e.g.
|
1 2 |
user> (what-pattern :block 'b2) {:block b2} |
supporters returns a list of items supporting a given block, and again the map structure in the Clojure sample makes a different approach necessary. We are filtering for the given block (a possible call would be: (supporters 'b1)) and possible :supports or :supported-by keys in database. The output of this function is then used by supp-cube where we query the results of supporters for them being cubes. Basically here the same things are happening like in the Lisp code, but it’s places like this where you recognize the difference between Clojure and its ancestor.
Since we’ve been so hard-working, we are able to skip all following exercises, because they can be solved with simple fetch calls. This concludes chapter 7.
