{"id":413,"date":"2012-09-07T22:40:04","date_gmt":"2012-09-07T12:40:04","guid":{"rendered":"http:\/\/juliangamble.com\/blog\/?p=413"},"modified":"2013-12-27T10:47:46","modified_gmt":"2013-12-26T23:47:46","slug":"the-little-schemer-in-clojure-chapter-8-friends-and-relations","status":"publish","type":"post","link":"https:\/\/juliangamble.com\/blog\/2012\/09\/07\/the-little-schemer-in-clojure-chapter-8-friends-and-relations\/","title":{"rendered":"The Little Schemer in Clojure \u2013 Chapter 8 \u2013 Friends and Relations"},"content":{"rendered":"

This is the eighth Chapter of a series of posts about porting\u00a0The Little Schemer<\/a>\u00a0to Clojure. You may wish to\u00a0read the intro<\/a>.<\/em><\/p>\n

So far we’ve covered\u00a0flat data structures<\/a>,\u00a0reading flat data structures<\/a>,\u00a0creating data structures<\/a>,\u00a0creating a numeric tower<\/a>, working with\u00a0multiple occurrences of a match in the list<\/a>, \u00a0changing our functions to work with nested lists<\/a>\u00a0and building a numerical expression evaluator<\/a>.<\/p>\n

This chapter we’ll look at sets, relations and functions (in the mathematical sense). \u00a0So starting with set?<\/code> let’s see if a list contains a set of unique items.<\/p>\n

\r\n(def set_?\r\n  (fn [lat]\r\n    (cond\r\n      (null? lat) true\r\n      true (cond\r\n             (member? (first lat) (rest lat)) false\r\n             true (set_? (rest lat))))))\r\n\r\n(println (set_? '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (set_? '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n<\/pre>\n
Note that this assumes the implementation of member?<\/code> from Chapter 5<\/a>.<\/p>\n
Now let’s simplify our definition of set?<\/code>:<\/p>\n
\r\n(def member\r\n  (fn [lat]\r\n    (cond\r\n      (null? lat) true\r\n      (member? (first lat) (rest lat)) false\r\n      true (set? (rest lat)))))\r\n\r\n(println (set_? '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (set_? '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n<\/pre>\n
Now given a non-unique list of items, let’s return a set of unique items based on the original list with makeset<\/code>:<\/p>\n
\r\n(def makeset\r\n  (fn [lat]\r\n    (cond\r\n      (null? lat) '()\r\n      (member? (first lat) (rest lat)) (makeset (rest lat))\r\n      true (cons (first lat) (makeset (rest lat))))))\r\n\r\n(println (makeset '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=> (toasted banana bread with butter for breakfast)\r\n(println (set_? (makeset '(breakfast toasted banana bread with butter for breakfast))))\r\n;\/\/=>true\r\n<\/pre>\n
Now we’ll refactor makeset using our definition of multirember<\/code> from Chapter 5<\/a>:<\/p>\n
\r\n(def makeset\r\n  (fn [lat]\r\n    (cond\r\n      (null? lat) '()\r\n      true (cons (first lat) (makeset (multirember (first lat) (rest lat)))))))\r\n\r\n(println "")\r\n(println "makeset - refactored with multirember")\r\n(println (makeset '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=> (breakfast toasted banana bread with butter for)\r\n; note other way around\r\n(println (set_? (makeset '(breakfast toasted banana bread with butter for breakfast))))\r\n;\/\/=>true\r\n<\/pre>\n
While we’re looking at sets, let’s write a function to work out if one set is a subset<\/code> of another:<\/p>\n
\r\n(def subset?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) true\r\n      true (cond\r\n             (member? (first set1) set2) (subset? (rest set1) set2)\r\n             true false))))\r\n\r\n(println (subset? '(banana butter) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (subset? '(banana butter) '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (subset? '(peanut butter) '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll refactor subset<\/code> to remove the second conditional:<\/p>\n
\r\n(def subset?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) true\r\n      (member? (first set1) set2) (subset? (rest set1) set2)\r\n      true false)))\r\n\r\n(println (subset? '(banana butter) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (subset? '(banana butter) '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (subset? '(peanut butter) '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll refactor subset<\/code> again to make better use of the trailing final condition:<\/p>\n
\r\n(def subset?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) true\r\n      true (and\r\n             (member? (first set1) set2)\r\n             (subset? (rest set1) set2)))))\r\n\r\n(println (subset? '(banana butter) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (subset? '(banana butter) '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (subset? '(peanut butter) '(toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll write eqset<\/code> to see if two sets are equal (regardless of order):<\/p>\n
\r\n(def eqset?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (subset? set1 set2) (subset? set2 set1)\r\n      true false)))\r\n\r\n(println (eqset? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n(println (eqset? '(toasted banana bread) '(toasted banana bread)))\r\n;\/\/=>true\r\n(println (subset? '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll refactor eqset<\/code> to have only one condition line:<\/p>\n
\r\n(def eqset?\r\n  (fn [set1 set2]\r\n    (cond\r\n      true (and\r\n             (subset? set1 set2)\r\n             (subset? set2 set1)))))\r\n\r\n(println (eqset? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n(println (eqset? '(toasted banana bread) '(toasted banana bread)))\r\n;\/\/=>true\r\n(println (subset? '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll refactor eqset<\/code> to remove the condition line altogether:<\/p>\n
\r\n(def eqset?\r\n  (fn [set1 set2]\r\n      (and\r\n        (subset? set1 set2)\r\n        (subset? set2 set1))))\r\n\r\n(println (eqset? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>false\r\n(println (eqset? '(toasted banana bread) '(toasted banana bread)))\r\n;\/\/=>true\r\n(println (subset? '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll write a test to see if two sets intersect?<\/code>:<\/p>\n
\r\n(def intersect?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) false\r\n      true (cond\r\n             (member? (first set1) set2) true\r\n             true (intersect? (rest set1) set2)))))\r\n\r\n(println (intersect? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (intersect? '(toasted banana bread) '(toasted banana bread)))\r\n;\/\/=>true\r\n(println (intersect? '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>true\r\n(println (intersect? '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll refactor intersect? to remove the redundant second conditional:<\/p>\n
\r\n(def intersect?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) false\r\n      (member? (first set1) set2) true\r\n      true (intersect? (rest set1) set2))))\r\n\r\n(println (intersect? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (intersect? '(toasted banana bread) '(toasted banana bread)))\r\n;\/\/=>true\r\n(println (intersect? '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>true\r\n(println (intersect? '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll refactor intersect? to make better use of the trailing conditional:<\/p>\n
\r\n(def intersect?\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) false\r\n      true (or\r\n             (member? (first set1) set2)\r\n             (intersect? (rest set1) set2)))))\r\n\r\n(println (intersect? '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>true\r\n(println (intersect? '(toasted banana bread) '(toasted banana bread)))\r\n;\/\/=>true\r\n(println (intersect? '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>true\r\n(println (intersect? '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>false\r\n<\/pre>\n
Now we’ll actually get the values at the intersect<\/code>ion:<\/p>\n
\r\n(def intersect\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) '()\r\n      (member? (first set1) set2) (cons (first set1) (intersect (rest set1) set2))\r\n      true (intersect (rest set1) set2))))\r\n\r\n(println (intersect '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>(toasted banana bread)\r\n(println (intersect '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>(toasted)\r\n(println (intersect '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>()\r\n<\/pre>\n
Now we’ll refactor intersect<\/code> to filter out non-members first:<\/p>\n
\r\n(def intersect\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) '()\r\n      (not (member? (first set1) set2)) (intersect (rest set1) set2)\r\n      true (cons (first set1) (intersect (rest set1) set2)))))\r\n\r\n(println (intersect '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>(toasted banana bread)\r\n(println (intersect '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>(toasted)\r\n(println (intersect '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>()\r\n<\/pre>\n
The opposite of getting the intersection of two sets is to get the union<\/code> – we’ll do that now:<\/p>\n
\r\n(def union\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) set2\r\n      (member? (first set1) set2) (union (rest set1) set2)\r\n      true (cons (first set1) (union (rest set1) set2)))))\r\n\r\n(println (union '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>(breakfast toasted banana bread with butter for breakfast)\r\n;\/\/ note not a set since not given a set\r\n(println (union '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>(peanut butter for breakfast toasted banana bread)\r\n(println (union '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>(strawberry yoghurt toasted banana bread)\r\n<\/pre>\n
The function next in the line is the complement<\/code> of two sets:<\/p>\n
\r\n(def complement_\r\n  (fn [set1 set2]\r\n    (cond\r\n      (null? set1) '()\r\n      (member? (first set1) set2) (complement_ (rest set1) set2)\r\n      true (cons (first set1) (complement_ (rest set1) set2)))))\r\n\r\n(println (complement_ '(toasted banana bread) '(breakfast toasted banana bread with butter for breakfast)))\r\n;\/\/=>()\r\n(println (complement_ '(toasted peanut butter for breakfast) '(toasted banana bread )))\r\n;\/\/=>(peanut butter for breakfast)\r\n(println (complement_ '(strawberry yoghurt) '(toasted banana bread )))\r\n;\/\/=>(strawberry yoghurt)\r\n<\/pre>\n
Now we’ll look at the intersection of more than two sets with intersect-all<\/code>:<\/p>\n
\r\n(def intersect-all\r\n  (fn [l-set]\r\n    (cond\r\n      (null? (rest l-set)) (first l-set)\r\n      true (intersect (first l-set) (intersect-all (rest l-set))))))\r\n\r\n(println "")\r\n(println "intersect-all")\r\n(println (intersect-all\r\n           '(\r\n              (toasted banana bread)\r\n              (breakfast toasted banana bread with butter for breakfast)\r\n              (toasted peanut butter for breakfast)\r\n              (toasted banana bread ))))\r\n;\/\/=>(toasted)\r\n<\/pre>\n
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<\/code> and second<\/code> value out of a pair:<\/p>\n
\r\n(def first_\r\n  (fn [p]\r\n    (cond\r\n      true (first p))))\r\n\r\n(println (first_ '(a b)))\r\n;\/\/=>a\r\n\r\n(def second_\r\n  (fn [p]\r\n    (cond\r\n      true (first (rest p)))))\r\n\r\n(println (second_ '(a b)))\r\n;\/\/=>b\r\n<\/pre>\n
Next we’ll add the ability to build<\/code> a pair:<\/p>\n
\r\n(def build\r\n  (fn [a b]\r\n    (cond\r\n      true (cons a (cons b '())))))\r\n\r\n(println (build 'a 'b))\r\n;\/\/=>(a b)\r\n<\/pre>\n
For the sake of keeping our brain going – we’ll get the third<\/code> item of a pair just to keep you wondering:<\/p>\n
\r\n(def third_\r\n  (fn [p]\r\n    (cond\r\n      true (first (rest (rest p))))))\r\n\r\n(println (third_ '(a b c)))\r\n;\/\/=>c\r\n<\/pre>\n
Now we’ll look closer at functions. You’ll remember that for a set of pairs to be a fun<\/code>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*<\/code> from Chapter 6<\/a>.<\/p>\n
\r\n(def firsts\r\n  (fn [l]\r\n    (cond\r\n      (empty? l) '()\r\n      true (cons (first (first l))\r\n        (firsts (rest l))))))\r\n\r\n(println "")\r\n(println "firsts")\r\n(println (firsts '((8 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>(8 4 7 6 3)\r\n\r\n(def fun?\r\n  (fn [rel]\r\n    (set? (firsts rel))))\r\n\r\n(println "")\r\n(println "fun? - refactored to use set? and firsts")\r\n(println (fun? '((4 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>false\r\n(println (fun? '((8 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>true\r\n(println (fun? '((8 3)(4 2)(7 1)(6 0)(9 5))))\r\n;\/\/=>true\r\n<\/pre>\n
Now just in case you ever wanted to reverse the elements in their pairs and order in the list – we bring you revrel<\/code>. (It is actually a building block for other functions to come).<\/p>\n
\r\n(def revrel\r\n  (fn [rel]\r\n    (cond\r\n      (null? rel) '()\r\n      true (cons\r\n             (build\r\n               (second_ (first rel))\r\n               (first_ (first rel)))\r\n             (revrel (rest rel))))))\r\n\r\n(println (revrel '((4 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>((3 4) (2 4) (6 7) (2 6) (4 3))\r\n(println (revrel '((8 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>((3 8) (2 4) (6 7) (2 6) (4 3))\r\n(println (revrel '((8 3)(4 2)(7 1)(6 0)(9 5))))\r\n;\/\/=>((3 8) (2 4) (1 7) (0 6) (5 9))\r\n<\/pre>\n
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?<\/code>:<\/p>\n
\r\n(def fullfun?\r\n  (fn [fun]\r\n    (set_? (seconds_ fun))))\r\n\r\n(println (fullfun? '((4 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>false\r\n(println (fullfun? '((8 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>false\r\n(println (fullfun? '((8 3)(4 2)(7 1)(6 0)(9 5))))\r\n;\/\/=>true\r\n<\/pre>\n
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<\/code>:<\/p>\n
\r\n(def one-to-one?\r\n  (fn [fun]\r\n    (fun? (revrel fun))))\r\n\r\n(println (one-to-one? '((4 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>false\r\n(println (one-to-one? '((8 3)(4 2)(7 6)(6 2)(3 4))))\r\n;\/\/=>false\r\n(println (one-to-one? '((8 3)(4 2)(7 1)(6 0)(9 5))))\r\n<\/pre>\n
You can see this running here<\/a>.<\/p>\n
Conclusion<\/strong>:
\nThis 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!).<\/p>\n
In total our primitives so far are: atom?<\/code>, null?<\/code>, first<\/code>, rest<\/code>, cond<\/code>, fn<\/code>, def<\/code>, empty?<\/code>,=<\/code>, cons<\/code>, add1,<\/code>, sub1<\/code>, one?<\/code> and expt<\/code>. These are all the functions (and those in the chapters to come) that we\u2019ll need to implement to get our metacircular interpreter working.<\/p>\n","protected":false},"excerpt":{"rendered":"
This is the eighth Chapter of a series of posts about porting\u00a0The Little Schemer\u00a0to Clojure. You may wish to\u00a0read the intro. So far we’ve covered\u00a0flat data structures,\u00a0reading flat data structures,\u00a0creating data structures,\u00a0creating a numeric tower, working with\u00a0multiple occurrences of a … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[3,12],"tags":[],"class_list":["post-413","post","type-post","status-publish","format-standard","hentry","category-clojure","category-thelittleschemer"],"_links":{"self":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/413","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/comments?post=413"}],"version-history":[{"count":13,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/413\/revisions"}],"predecessor-version":[{"id":573,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/413\/revisions\/573"}],"wp:attachment":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/media?parent=413"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/categories?post=413"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/tags?post=413"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}