*This is the eighth Chapter of a series of posts about porting The Little Schemer to Clojure. You may wish to read the intro.*

So far we’ve covered flat data structures, reading flat data structures, creating data structures, creating a numeric tower, working with multiple occurrences of a match in the list, changing our functions to work with nested lists and building a numerical expression evaluator.

This chapter we’ll look at sets, relations and functions (in the mathematical sense). So starting with `set?`

let’s see if a list contains a set of unique items.

(def set_? (fn [lat] (cond (null? lat) true true (cond (member? (first lat) (rest lat)) false true (set_? (rest lat)))))) (println (set_? '(toasted banana bread with butter for breakfast))) ;//=>true (println (set_? '(breakfast toasted banana bread with butter for breakfast))) ;//=>false

Note that this assumes the implementation of `member?`

from Chapter 5.

Now let’s simplify our definition of `set?`

:

(def member (fn [lat] (cond (null? lat) true (member? (first lat) (rest lat)) false true (set? (rest lat))))) (println (set_? '(toasted banana bread with butter for breakfast))) ;//=>true (println (set_? '(breakfast toasted banana bread with butter for breakfast))) ;//=>false

Now given a non-unique list of items, let’s return a set of unique items based on the original list with `makeset`

:

(def makeset (fn [lat] (cond (null? lat) '() (member? (first lat) (rest lat)) (makeset (rest lat)) true (cons (first lat) (makeset (rest lat)))))) (println (makeset '(breakfast toasted banana bread with butter for breakfast))) ;//=> (toasted banana bread with butter for breakfast) (println (set_? (makeset '(breakfast toasted banana bread with butter for breakfast)))) ;//=>true

Now we’ll refactor makeset using our definition of `multirember`

from Chapter 5:

(def makeset (fn [lat] (cond (null? lat) '() true (cons (first lat) (makeset (multirember (first lat) (rest lat))))))) (println "") (println "makeset - refactored with multirember") (println (makeset '(breakfast toasted banana bread with butter for breakfast))) ;//=> (breakfast toasted banana bread with butter for) ; note other way around (println (set_? (makeset '(breakfast toasted banana bread with butter for breakfast)))) ;//=>true

While we’re looking at sets, let’s write a function to work out if one set is a `subset`

of another:

(def subset? (fn [set1 set2] (cond (null? set1) true true (cond (member? (first set1) set2) (subset? (rest set1) set2) true false)))) (println (subset? '(banana butter) '(breakfast toasted banana bread with butter for breakfast))) ;//=>true (println (subset? '(banana butter) '(toasted banana bread with butter for breakfast))) ;//=>true (println (subset? '(peanut butter) '(toasted banana bread with butter for breakfast))) ;//=>false

Now we’ll refactor `subset`

to remove the second conditional:

(def subset? (fn [set1 set2] (cond (null? set1) true (member? (first set1) set2) (subset? (rest set1) set2) true false))) (println (subset? '(banana butter) '(breakfast toasted banana bread with butter for breakfast))) ;//=>true (println (subset? '(banana butter) '(toasted banana bread with butter for breakfast))) ;//=>true (println (subset? '(peanut butter) '(toasted banana bread with butter for breakfast))) ;//=>false

Now we’ll refactor `subset`

again to make better use of the trailing final condition:

(def subset? (fn [set1 set2] (cond (null? set1) true true (and (member? (first set1) set2) (subset? (rest set1) set2))))) (println (subset? '(banana butter) '(breakfast toasted banana bread with butter for breakfast))) ;//=>true (println (subset? '(banana butter) '(toasted banana bread with butter for breakfast))) ;//=>true (println (subset? '(peanut butter) '(toasted banana bread with butter for breakfast))) ;//=>false

Now we’ll write `eqset`

to see if two sets are equal (regardless of order):

(def eqset? (fn [set1 set2] (cond (subset? set1 set2) (subset? set2 set1) true false))) (println (eqset? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>false (println (eqset? '(toasted banana bread) '(toasted banana bread))) ;//=>true (println (subset? '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>false

Now we’ll refactor `eqset`

to have only one condition line:

(def eqset? (fn [set1 set2] (cond true (and (subset? set1 set2) (subset? set2 set1))))) (println (eqset? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>false (println (eqset? '(toasted banana bread) '(toasted banana bread))) ;//=>true (println (subset? '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>false

Now we’ll refactor `eqset`

to remove the condition line altogether:

(def eqset? (fn [set1 set2] (and (subset? set1 set2) (subset? set2 set1)))) (println (eqset? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>false (println (eqset? '(toasted banana bread) '(toasted banana bread))) ;//=>true (println (subset? '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>false

Now we’ll write a test to see if two sets `intersect?`

:

(def intersect? (fn [set1 set2] (cond (null? set1) false true (cond (member? (first set1) set2) true true (intersect? (rest set1) set2))))) (println (intersect? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>true (println (intersect? '(toasted banana bread) '(toasted banana bread))) ;//=>true (println (intersect? '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>true (println (intersect? '(strawberry yoghurt) '(toasted banana bread ))) ;//=>false

Now we’ll refactor intersect? to remove the redundant second conditional:

(def intersect? (fn [set1 set2] (cond (null? set1) false (member? (first set1) set2) true true (intersect? (rest set1) set2)))) (println (intersect? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>true (println (intersect? '(toasted banana bread) '(toasted banana bread))) ;//=>true (println (intersect? '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>true (println (intersect? '(strawberry yoghurt) '(toasted banana bread ))) ;//=>false

Now we’ll refactor intersect? to make better use of the trailing conditional:

(def intersect? (fn [set1 set2] (cond (null? set1) false true (or (member? (first set1) set2) (intersect? (rest set1) set2))))) (println (intersect? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>true (println (intersect? '(toasted banana bread) '(toasted banana bread))) ;//=>true (println (intersect? '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>true (println (intersect? '(strawberry yoghurt) '(toasted banana bread ))) ;//=>false

Now we’ll actually get the values at the `intersect`

ion:

(def intersect (fn [set1 set2] (cond (null? set1) '() (member? (first set1) set2) (cons (first set1) (intersect (rest set1) set2)) true (intersect (rest set1) set2)))) (println (intersect '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>(toasted banana bread) (println (intersect '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>(toasted) (println (intersect '(strawberry yoghurt) '(toasted banana bread ))) ;//=>()

Now we’ll refactor `intersect`

to filter out non-members first:

(def intersect (fn [set1 set2] (cond (null? set1) '() (not (member? (first set1) set2)) (intersect (rest set1) set2) true (cons (first set1) (intersect (rest set1) set2))))) (println (intersect '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>(toasted banana bread) (println (intersect '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>(toasted) (println (intersect '(strawberry yoghurt) '(toasted banana bread ))) ;//=>()

The opposite of getting the intersection of two sets is to get the `union`

– we’ll do that now:

(def union (fn [set1 set2] (cond (null? set1) set2 (member? (first set1) set2) (union (rest set1) set2) true (cons (first set1) (union (rest set1) set2))))) (println (union '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>(breakfast toasted banana bread with butter for breakfast) ;// note not a set since not given a set (println (union '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>(peanut butter for breakfast toasted banana bread) (println (union '(strawberry yoghurt) '(toasted banana bread ))) ;//=>(strawberry yoghurt toasted banana bread)

The function next in the line is the `complement`

of two sets:

(def complement_ (fn [set1 set2] (cond (null? set1) '() (member? (first set1) set2) (complement_ (rest set1) set2) true (cons (first set1) (complement_ (rest set1) set2))))) (println (complement_ '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast))) ;//=>() (println (complement_ '(toasted peanut butter for breakfast) '(toasted banana bread ))) ;//=>(peanut butter for breakfast) (println (complement_ '(strawberry yoghurt) '(toasted banana bread ))) ;//=>(strawberry yoghurt)

Now we’ll look at the intersection of more than two sets with `intersect-all`

:

(def intersect-all (fn [l-set] (cond (null? (rest l-set)) (first l-set) true (intersect (first l-set) (intersect-all (rest l-set)))))) (println "") (println "intersect-all") (println (intersect-all '( (toasted banana bread) (breakfast toasted banana bread with butter for breakfast) (toasted peanut butter for breakfast) (toasted banana bread )))) ;//=>(toasted)

Here the book changes direction – our work on sets has been a building block for looking at functions and relations. Assuming that we can express a function as a set of value pairs – we need to be able to have the building blocks to work with pairs. We’ll start by getting the `first`

and `second`

value out of a pair:

(def first_ (fn [p] (cond true (first p)))) (println (first_ '(a b))) ;//=>a (def second_ (fn [p] (cond true (first (rest p))))) (println (second_ '(a b))) ;//=>b

Next we’ll add the ability to `build`

a pair:

(def build (fn [a b] (cond true (cons a (cons b '()))))) (println (build 'a 'b)) ;//=>(a b)

For the sake of keeping our brain going – we’ll get the `third`

item of a pair just to keep you wondering:

(def third_ (fn [p] (cond true (first (rest (rest p)))))) (println (third_ '(a b c))) ;//=>c

Now we’ll look closer at functions. You’ll remember that for a set of pairs to be a `fun`

ction, there must be only one domain value – ie the first values from a set of pairs must themselves be a set. We’ll borrow our definition of `member*`

from Chapter 6.

(def firsts (fn [l] (cond (empty? l) '() true (cons (first (first l)) (firsts (rest l)))))) (println "") (println "firsts") (println (firsts '((8 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>(8 4 7 6 3) (def fun? (fn [rel] (set? (firsts rel)))) (println "") (println "fun? - refactored to use set? and firsts") (println (fun? '((4 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>false (println (fun? '((8 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>true (println (fun? '((8 3)(4 2)(7 1)(6 0)(9 5)))) ;//=>true

Now just in case you ever wanted to reverse the elements in their pairs and order in the list – we bring you `revrel`

. (It is actually a building block for other functions to come).

(def revrel (fn [rel] (cond (null? rel) '() true (cons (build (second_ (first rel)) (first_ (first rel))) (revrel (rest rel)))))) (println (revrel '((4 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>((3 4) (2 4) (6 7) (2 6) (4 3)) (println (revrel '((8 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>((3 8) (2 4) (6 7) (2 6) (4 3)) (println (revrel '((8 3)(4 2)(7 1)(6 0)(9 5)))) ;//=>((3 8) (2 4) (1 7) (0 6) (5 9))

So applying what we’ve just learned – a full function is one in which both the values of the domain are unique, and the values of the range are unique. We can test this with `fullfun?`

:

(def fullfun? (fn [fun] (set_? (seconds_ fun)))) (println (fullfun? '((4 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>false (println (fullfun? '((8 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>false (println (fullfun? '((8 3)(4 2)(7 1)(6 0)(9 5)))) ;//=>true

A simpler way to express this idea is that the domain of the function is unique – even if the range values are swapped with the domain values – we call this `one-to-one`

:

(def one-to-one? (fn [fun] (fun? (revrel fun)))) (println (one-to-one? '((4 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>false (println (one-to-one? '((8 3)(4 2)(7 6)(6 2)(3 4)))) ;//=>false (println (one-to-one? '((8 3)(4 2)(7 1)(6 0)(9 5))))

You can see this running here.

**Conclusion**:

This chapter we’ve looked at sets, relations and functions (in the mathematical sense). We haven’t really added any new primitives this chapter (thank goodness!).

In total our primitives so far are: `atom?`

, `null?`

, `first`

, `rest`

, `cond`

, `fn`

, `def`

, `empty?`

,`=`

, `cons`

, `add1,`

, `sub1`

, `one?`

and `expt`

. These are all the functions (and those in the chapters to come) that we’ll need to implement to get our metacircular interpreter working.

## 3 thoughts on “The Little Schemer in Clojure – Chapter 8 – Friends and Relations”