# The Little Schemer in Clojure – Chapter 8 – Friends and Relations

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

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)))
(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)))
(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
'(
(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”

This site uses Akismet to reduce spam. Learn how your comment data is processed.