Monday, March 26, 2012

On Lisp in Clojure ch 4 (4.1 to 4.3)

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure.

While I was trying to figure out how to implement the prune function in section 4.4, I ran across this post my Michael Fogus: Rather than parrot things I don't entirely understand, I will refer the reader to his post. Fogus seemed to stick mostly to section 4.4, so I will cover the other sections here.

Fogus also wrote a post on Chapter 5.

Section 4.1 Birth of a Utility

The examples didn't implement the nicknames function, so I didn't either. As a result, these examples won't actually compile. My all-nicknames implementation assmes that the nicknames function returns a map with the full names as keys, and lists of nicknames as values.

;; this won't compile because nicknames function doesn't exist
;; I am assuming that nicknames will return a list with the name
;; and the matching nicknames
(defn all-nicknames [names]
  ( loop [names names acc {}]
    (if (empty? names)
      (recur (rest names) (conj (nicknames (first names) acc))))))

;; shorter version
(map nicknames people)

I skipped down to the find2 function in the next set of examples. I did bars instead of bookstores because I can't name bookstores by town. Besides, it allowed a gratuitous Taco Mac reference. This example does work. (This was my first time using if-let, so I had to make sure I was doing it right.)

(defn find2 [fn lst]
  (if (empty? lst)
    (if-let [val (fn (first lst))]
      {(first lst) val}
      (recur fn (rest lst)))))

(def bars {:atlanta '(taco-mac) :boston '(cheers)  })

(defn return-bars [town]
  (town bars))

(find2 return-bars [:chicago :atlanta)

Section 4.2 Invest in Abstratction

;; compare the length of 2 collections
(> (count [1 2 3]) (count [1 2]))

;; join lists together before mapping over them
(map even? (reduce into '([1 2] [3 4] [5 6])))

Section 4.3 Operations on Lists

The first block of examples illustrate some ways that Clojure is different thatn CLISP. As I understand it, (last '(1 2 3)) would return (3 . nil) in Common Lisp hence the (car (last lst)). In Clojure, (last '(1 2 3)) returns 3. Because of the different structure, the single function doesn't make any sense in Clojure.

The next two functions in the block, append1 and conc1, add an item to a list. conc1 mutates the list and append1 returns a new list. Clojure has a function called conj, which works with each of the Clojure collections appending to the head of a list or tail of a vector. Maps and sets don't keep track of the insert order, but you can add to them as well.

(conj [1 2 3] 4) ;; vector => [1 2 3 4]
(conj '(2 3 4) 1) ;; list => '(1 2 3 4)
(conj #{1 2 3} 4) ;; set => #{1 2 3 4}

Data structures are immutable by default in Clojure, so conj returns a copy of a new collection instead of modifying the collection in place.

The mklst function can be implemented the same way in Clojure if you absolutely want the item in a list, even if the item is already another collection.

(defn mklist [obj]
  (if (list? obj) obj (list obj)))
If you only care that the item is inside of a collection so you can treat it with functions that work on sequences, you can test for sequential?
(defn mklist [obj]
  (if (sequential? obj) obj (list obj)))
Either one can be used with his mapped example:
(map #(mklist (lookup %)) data)

His next example was to use a filter to return 1+ x for each number in a list. In Clojure filter returns the term that returned a true value, not the true value itself. So this function would be written:

(map inc
      (fn [x] (instance? Number x))
      ['a 1 2 'b 3 'c 'd  4]) )

If we wanted to add 2 to each number, we could use "partial" as Jacek pointed out in the comments of the last post.

(map (partial + 2)
     (filter (fn [x] (instance? Number x))
          ['a 1 2 'b 3 'c 'd 4]))

The next block of examples all use recursion to work with a list. The longer function walks through 2 lists until the shorter one is exhausted.

(defn longer? [x y]
  (if (or (empty? x) (empty? y))
    (not (empty? x))
    (recur (rest x) (rest y))))

The next example is his filter function. Clojure avoids a lot of recursion by using lazy sequences. Each term is only realized as it is required. So in Clojure, you could get items from an infinite list of odd numbers like this:

(take 5 (filter odd? (iterate inc 1)))
His group function is also implemented in Clojure in a lazy way.
(partition 2 [1 2 3 4 5])
;; ((1 2) (3 4))
(partition-all 2 [1 2 3 4 5])
;; ((1 2) (3 4) (5))
(take 5 (partition 2 (iterate inc 1)))
;; ((1 2) (3 4) (5 6) (7 8) (9 10))

Section 4.4 Search

While researching the examples for this section I discovered that Michael Fogus had already translated these examples in his blog. He covered the section much better than I can. In my next post, I will pick things up again in section 4.5.

No comments:

Post a Comment