{"id":346,"date":"2012-08-19T15:51:28","date_gmt":"2012-08-19T05:51:28","guid":{"rendered":"http:\/\/juliangamble.com\/blog\/?p=346"},"modified":"2013-12-27T10:38:20","modified_gmt":"2013-12-26T23:38:20","slug":"the-little-schemer-in-clojure-chapter-6-oh-my-gawd-its-full-of-stars","status":"publish","type":"post","link":"https:\/\/juliangamble.com\/blog\/2012\/08\/19\/the-little-schemer-in-clojure-chapter-6-oh-my-gawd-its-full-of-stars\/","title":{"rendered":"The Little Schemer in Clojure – Chapter 6 – *Oh My Gawd*: It’s Full of Stars"},"content":{"rendered":"

This is the sixth 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 flat data structures<\/a>, reading flat data structures<\/a>, creating data structures<\/a>, creating a numeric tower<\/a>, and working with multiple occurrences of a match in the list<\/a>.<\/p>\n

What about nested lists? Would our functions work for those? Not yet. This chapter we’ll fix that.<\/p>\n

First we’ll look at leftmost<\/code> (which also involves defining non-atom?<\/code> and not<\/code>). The point of this function is to find the leftmost S-expression, even if it is an empty list ().<\/p>\n

\r\n(def not_\r\n  (fn [b]\r\n    (cond\r\n      b false\r\n      true true)))\r\n\r\n(println (not_ (= 'a 'b)))\r\n\r\n(def non-atom?\r\n  (fn [s]\r\n    (not_ (atom? s))))\r\n\r\n(println (non-atom? (quote thai)))\r\n\r\n(def leftmost\r\n  (fn [l]\r\n    (println "(leftmost " l)\r\n    (println (non-atom? l))\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l)) (leftmost (first l))\r\n      true (first l))))\r\n\r\n(println (leftmost (quote ((((pad))thai))chicken())))\r\n<\/pre>\n
Now we’ll write rember*<\/code>. What we’re doing here is to remove all matching list members from within the nested list.<\/p>\n
\r\n(def rember*\r\n  (fn [a l]\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l)) (cons (rember* a (first l)) (rember* a (rest l)))\r\n      true (cond\r\n             (= (first l) a) (rember* a (rest l))\r\n             true (cons (first l) (rember* a (rest l)))))))\r\n\r\n(println (rember* 'bacon '(((bbq sauce)) (with (egg and (bacon))))))\r\n<\/pre>\n
Now we’ll do insertR*.<\/code>\u00a0The point of this one is to insert a new element to the right of the matching element, no matter where is occurs in the nested list.<\/p>\n
\r\n(def insertR*\r\n  (fn [new old l]\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l)) (cons (insertR* new old (first l)) (insertR* new old (rest l)))\r\n      true (cond\r\n             (= (first l) old) (cons old (cons new (insertR* new old (rest l))))\r\n             true (cons (first l) (insertR* new old (rest l)))))))\r\n\r\n(println (insertR* 'chicken 'baked '(((baked)) (with roast) vegetables)))\r\n<\/pre>\n
Well it is time for another Commandment. Well it would be, but instead we’re going to revise an existing one. Here goes:<\/p>\n
When recurring on a list of atoms, lat<\/code>, or a vec, vec<\/code>, ask two questions about them, and use (rest lat)<\/code> or (rest vec)<\/code> for the natural recursion.<\/p>\n
When recurring on a list of S-expressions, l<\/code>, ask three questions: (null? l)<\/code>, (atom? (first l))<\/code>, and (non-atom? (first l))<\/code>; and use (first l)<\/code> and (rest l)<\/code> for the natural recursion.<\/p>\n
When recurring on a number, n<\/code>, ask two questions, and use (sub1 n)<\/code> for the natural recursion.<\/p>\n
So what happened there? We extended our recursion checks to be able to handle nested lists.<\/p>\n
Now let’s do occur*.<\/code>\u00a0The point of this one is to count the occurrences of a matching list member inside a nested list.<\/p>\n
\r\n(def occur*\r\n  (fn [a l]\r\n    (cond\r\n      (null? l) 0\r\n      (non-atom? (first l)) (+_ (occur* a (first l)) (occur* a (rest l)))\r\n      true (cond\r\n             (= (first l) a) (add1 (occur* a (rest l)))\r\n             true (occur* a (rest l))))))\r\n\r\n(println (occur* 'creamy '(((creamy)) new (york (cheesecake)) with a ((creamy) latte))))\r\n<\/pre>\n
Now we’ll do subst*<\/code>. What we want to achieve is a find and replace inside a nested list.<\/p>\n
\r\n(def subst*\r\n  (fn [new old l]\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l)) (cons (subst* new old (first l)) (subst* new old (rest l)))\r\n      true (cond\r\n             (= (first l) old) (cons new (subst* new old (rest l)))\r\n             true (cons (first l) (subst* new old (rest l)))))))\r\n\r\n(println (subst* 'baked 'creamy '(((creamy) cheesecake) (with (hot (espresso))))))\r\n<\/pre>\n
Now let’s look at insertL<\/code>. This is quite similar to insertR<\/code> above – but now we insert the new value to the left of the matching value.<\/p>\n
\r\n(def insertL*\r\n  (fn [new old l]\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l))\r\n        (cons\r\n          (insertL* new old (first l))\r\n          (insertL* new old (rest l)))\r\n      true (cond\r\n        (= (first l) old)\r\n          (cons new\r\n            (cons old\r\n              (insertL*\r\n                new old (rest l))))\r\n        true (cons (first l)\r\n          (insertL*\r\n            new old (rest l)))))))\r\n\r\n(println (insertL* 'fresh 'creamy '(((creamy) cheesecake) (with (hot (espresso))))))\r\n<\/pre>\n
Now we’ll rewrite member*<\/code> without using the non-atom?<\/code> function:<\/p>\n
\r\n(def member*\r\n  (fn [a l]\r\n    (cond\r\n      (null? l) '()\r\n      (atom? (first l))\r\n        (or\r\n          (= (first l) a)\r\n          (member* a (rest l)))\r\n      true (or\r\n        (member* a (first l))\r\n        (member* a (rest l))))))\r\n\r\n(println (member* 'creamy '(((creamy) cheesecake) (with (hot (espresso))))))\r\n<\/pre>\n
Now we’ll look at testing list equality using eqlist?<\/code><\/p>\n
\r\n(def eqlist?\r\n  (fn [l1 l2]\r\n    (cond\r\n      (and (null? l1) (null? l2)) true\r\n      (or (null? l1) (null? l2)) false\r\n      (and (non-atom? (first l1)) (non-atom? (first l2)))\r\n        (and (eqlist? (first l1) (first l2))\r\n             (eqlist? (rest l1) (rest l2)))\r\n      (or (non-atom? (first l1)) (non-atom? (first l2))) false\r\n      true (and\r\n        (eqan? (first l1) (first l2))\r\n        (eqlist? (rest l1) (rest l2))))))\r\n\r\n(println (eqlist? '(with (hot (espresso))) '(with (hot (espresso)))));\/\/=>true\r\n(println (eqlist? '(with (hot (espresso))) '((creamy) cheesecake)));\/\/=>false\r\n<\/pre>\n
Now we’ll take a look at rember<\/code>. At this point the Chapter takes a brief digression from modifying algorithms handle nested lists to focus on the art of refactoring itself. This version of rember<\/code>\u00a0differs from the one before by removing a matching S-expression rather than the first matching atom.<\/p>\n
\r\n(def rember\r\n  (fn [s l]\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l))\r\n        (cond\r\n          (equal? (first l) s) (rest l)\r\n          true (cons (first l) (rember s (rest l))))\r\n      true (cond\r\n        (equal? (first l) s) (rest l)\r\n        true (cons (first l) (rember s (rest l)))))))\r\n\r\n(println (rember 'fresh '(((fresh creamy) cheesecake) (with (hot (espresso))))))\r\n;\/\/=> (((fresh creamy) cheesecake) (with (hot (espresso))))\r\n\r\n(println (rember 'fresh '(fresh creamy cheesecake with hot espresso)))\r\n;\/\/=> (creamy cheesecake with hot espresso)\r\n<\/pre>\n
Now we’ll do a refactor of rember<\/code>. The point here is just to illustrate simplification by removing redundant code.<\/p>\n
\r\n(def rember\r\n  (fn [s l]\r\n    (cond\r\n      (null? l) '()\r\n      true (cond\r\n        (equal? (first l) s) (rest l)\r\n        true (cons (first l) (rember s (rest l)))))))\r\n\r\n(println (rember 'fresh '(((fresh creamy) cheesecake) (with (hot (espresso))))))\r\n;\/\/=> (((fresh creamy) cheesecake) (with (hot (espresso))))\r\n\r\n(println (rember 'fresh '(fresh creamy cheesecake with hot espresso)))\r\n;\/\/=> (creamy cheesecake with hot espresso)\r\n<\/pre>\n
Now we’ll do a another refactor of rember<\/code>. Now we’re making it similar by pushing out the tests from the outer<\/code> cond to the inner.<\/p>\n
\r\n(def rember\r\n  (fn [s l]\r\n    (cond\r\n      (null? l) '()\r\n      (= (first l) s) (rest l)\r\n      true (cons (first l) (rember s (rest l)))))))\r\n\r\n(println (rember 'fresh '(((fresh creamy) cheesecake) (with (hot (espresso))))))\r\n;\/\/=> (((fresh creamy) cheesecake) (with (hot (espresso))))\r\n\r\n(println (rember 'fresh '(fresh creamy cheesecake with hot espresso)))\r\n;\/\/=> (creamy cheesecake with hot espresso)\r\n<\/pre>\n
Now we’ll take one more crack at refactoring insertL*<\/code>. This time by removing redundant code.<\/p>\n
\r\n(def insertL*\r\n  (fn [new old l]\r\n    (cond\r\n      (null? l) '()\r\n      (non-atom? (first l))\r\n        (cons\r\n          (insertL* new old (first l))\r\n          (insertL* new old (rest l)))\r\n      (= (first l) old)\r\n        (cons new\r\n          (cons old\r\n            (insertL*\r\n              new old (rest l))))\r\n      true (cons (first l)\r\n        (insertL*\r\n          new old (rest l))))))\r\n\r\n(println (insertL* 'fresh 'creamy '(((creamy) cheesecake) (with (hot (espresso))))))\r\n<\/pre>\n
Now we’ll look at another commandment:<\/p>\n
Simplify only after the function is correct<\/p>\n
In some ways obvious – in other ways so profound that Martin Fowler wrote a whole book about it<\/a>. The point is that optimisations of your code size are great – but get it working first.<\/p>\n
You can see it running here<\/a>.<\/p>\n
Conclusion:<\/strong>
\nHere we’ve adapted our existing functions to be able to work for multiple occurrences of the search result. This chapter we didn’t add any true primitives, not_<\/code> and non-atom<\/code> are entirely composed of existing primtives.<\/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> and one?<\/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 sixth 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 flat data structures, reading flat data structures, creating data structures, creating a numeric tower, and … 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-346","post","type-post","status-publish","format-standard","hentry","category-clojure","category-thelittleschemer"],"_links":{"self":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/346","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=346"}],"version-history":[{"count":30,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/346\/revisions"}],"predecessor-version":[{"id":571,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/posts\/346\/revisions\/571"}],"wp:attachment":[{"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/media?parent=346"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/categories?post=346"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/juliangamble.com\/blog\/wp-json\/wp\/v2\/tags?post=346"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}