Friday, 1 January 2010

ACL: Chapter 3

Well, the exercises at the end of chapter 3 really forced me to think. I had to really bend my brain to force it to think in functional, rather than imperative terms.

I have decided to try to provide answers to the exercises in the best idiomatic Clojure code that I can manage, including using the clojure-contrib library where possible. I think this is the best way for me to learn to think in Clojure.

Exercise 3 wasn't too bad. It just required a little bit of lateral thinking to implement the required functionality.
; exercise 3
; write a version of union that preserves the order
; of the original lists
(defn new-union [lst1 lst2]
  (distinct (interleave lst1 lst2)))
Exercise 4 really stumped me for a while. It was while doing this exercise that I realized how much work I had to do to think functionally, rather than imperatively. In the end I searched through the api docs to find something that implemented this functionality. I found clojure.contrib.seq-utils/frequencies and looked at the source code, which led me to the reduce function, and hence to the following solution:
; exercise 4
; define a function that takes a list
; and returns a list indicating the number
; of times each element appears, sorted
; from most common element to least
; common
(defn occurrences [lst]
  (sort-by val > (reduce 
                   (fn [counts x]
                     (assoc counts x (inc (get counts x 0))))
In my drive to attempt to write concise, idiomatic Clojure code, making use of libraries, I then re-wrote the function as:
; better version using clojure.contrib.seq-utils/frequencies
(defn better-occurences [lst]
  (sort-by val > (clojure.contrib.seq-utils/frequencies lst)))
That was blood worth sweating. It forced me to hunt through the api documentation, and taught me how to use reduce.

By the time I reached exercise 5 I was beginning to enjoy the power of the sequence library.
; exercise 5
; Suppose the function pos+ takes a list and returns a
; list of each element plus its position
; (pos+ '(7 5 1 4))
; (7 6 3 7)
; Define this function using a) recursion, b) iteration
; c) mapcar (not sure this exists in clojure)

; a) recursion
(defn recursive-pos+ 
  ([lst] (recursive-pos+ lst 0))
  ([lst pos]
    (if (empty? lst)
    (cons (+ pos (first lst)) (recursive-pos+ (rest lst) (inc pos))))))

; b) iteration
(defn iterative-pos+ [lst]
  (loop [result-list () working-list lst pos 0]
    (if (empty? working-list)
      (reverse result-list) ; yuck
      (recur (cons (+ pos (first working-list)) result-list)
        (rest working-list)
        (inc pos)))))

; c) with map - seems to do what mapcar would do
(defn map-pos+ [lst]
  (map (fn [x pos] (+ x pos)) lst (iterate inc 0)))
I just love the elegance of map-pos+.

After all that, exercise 8 came quite easily:
; exercise 8
; define a function that takes a list and prints it
; in dot notation
; (showdots '(a b c))
; (A . (B . (C . NIL)))
(defn showdots [lst]
  (if (empty? lst)
    (str "NIL")
    (str "(" (first lst) " . " (showdots (rest lst)) ")"))) 
As I said above, I've begun to appreciate the difference between thinking in imperative and functional terms. Working through these exercises I feel I am beginning to grok the functional approach. I have a long way to go, but the journey is proving fun.

No comments:

Post a Comment