Thursday, 31 December 2009

ACL: Chapter 2

Here is the code I wrote while working through Chapter 2. Some comments follow below:
;; recursion example from p.16
;; note empty? instead of null
;; explicitly return true / false instead of lst / nil
(defn our-member [obj lst]
  (if (empty? lst)
    false
    (if (= (first lst) obj)
      true
      (recur obj (rest lst)))))


;; ask-number example from p.20
;; this is the closest simple version I've come up with
;; doesn't work with the same input as the example in ACL
;; e.g. entering a leads to
;; CompilerException java.lang.Exception: Unable to resolve symbol: a in this context (NO_SOURCE_FILE:111)
;; the (eval (read)) is needed because (read) by itself returns something like
;; (eval '(do a))
;; appears to be a difference with ACL
(defn ask-number []
  (print "Please enter a number. ")
  (flush)
  (let [val (eval (read))]
    (if (number? val)
      val
      (recur))))


;; version of ask-number that works for the same inputs used in ACL
;; this wouldn't work in enclojure
(defn ask-number2 []
  (print "Please enter a number. ")
  (flush)
  (let [val (try (Integer/parseInt (read-line))
      (catch NumberFormatException nfe nil))]
    (if (number? val)
    val
    (recur))))

;; exercise 3
;; 3 different cons functions that return (a b c)
(cons 'a '(b c))
(cons 'a (cons 'b '(c)))
(cons 'a (cons 'b (cons 'c ())))

;; exercise 4
;; define a function that takes two arguments and returns the greater
;; of the two
(defn greater [x y]
  (if (> x y) x y))

;; exercise 7
;; using only operators defined in this chapter
;; define a function that takes a list as an argument
;; and returns true if one of its elements is a list
(defn contains-list? [lst]
  (if (empty? lst)
    false
    (if (list? (first lst))
      true
      (recur (rest lst)))))

;; exercise 8a
;; recursive and iterative function that takes an integer
;; and prints that many dots
;; since we are using recur there isn't really a huge difference
;; between the 2 implementations. loop/recur feels very like
;; the recursive call

;; recursive
(defn dots-recur [n]
  (if (zero? n)
    (println)
    (do
      (print ".")
      (recur (dec n)))))

;; iterative
(defn dots-iter [n]
  (loop [counter n]
    (if (zero? counter)
      (println)
      (do
        (print ".")
        (recur (dec counter))))))

;; recursive no recur
;; leads to stack overflow
(defn dots-recur-naive [n]
  (if (zero? n)
    (println)
    (do
      (print ".")
      (dots-recur-naive (dec n)))))


;; exercise 8b
;; function that takes a list and counts number of times a
;; appears in it

;; recursive
;; can't use recur here because not in tail position
;; therefore prone to stack overflow for long lists
(defn counta-recursive [lst]
  (if (empty? lst)
    0
    (+ (if (= (first lst) \a) 1 0) (counta (rest lst)))))


;; iterative
;; seems more natural to write it this way
(defn counta-iterative [lst]
  (loop [sublist lst total 0]
    (if (empty? sublist)
      total
      (recur (rest sublist) (+ total (if (= (first sublist) \a) 1 0))))))
Some observations based on what I learnt while working through chapter 2:
  1. It proved difficult to implement the ask-number function in Clojure. The read function seemed to return an unevaluated form, which I rationalized as making sense since it was returning a form to pass to eval. See the comments in the code above for more detail.
  2. Enclojure seemed to have problems with the read-line function. I was only able to make the ask-number2 function work in the repl started from my bash shell.
  3. The iterative/recursive functions in chapter 8 didn't feel hugely different in Clojure due to the explicit use of recur. However I did see the benefit of using an iterative algorithm in the counta example, since I couldn't use recur in the recursive implementation, making it vulnerable to stack overflow. 
  4. We don't really need to use iteration or recursion explicitly for the counta examples. An even better way to implement this function using the Clojure sequence library would be:
(defn counta-filter [lst]
  (count (filter #(= % \a) lst)))

No comments:

Post a Comment