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 intersection:

(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 function, 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.