read


read or learn more

On Lisp -> Clojure (Chapter 4)

Oct 8, 2008

; As always, I will post when the code is “complete”, but my progress can be followed on Github. Also, this post is executable, just copy and paste into a Clojure REPL.

Posts in this series: ch. 2, ch. 2 redux, ch. 3, ch. 4, ch. 5

; pg. 42

;; PG defines a general find function (find2) that given a function and a list, returns both the first matched value and the value returned from the matching function. The most direct translation to Clojure is:

;

(defn findr [f sq]
  (when (seq sq)
    (let [value (f (first sq))]
      (if (nil? value)
        (recur f (rest sq))
        [(first sq) value]))))

(defn evenr [elem]
  (if (even? elem)
    "is even"))

(findr evenr '(1 13 3 4))
(findr evenr '(1 13 3 5))
(findr evenr nil)
;

; pg. 45

;; L@@k: Why rseq not lazy.

;; Clojure really shines with a simple problem like this because it will work on lists, vectors, sorted maps, and strings.

;

(defn last1 [sq]
  (last s))
;

;; Test for a sequence of one element ;

(defn single [sq]
  (and (seq? sq) (not (rest sq))))
;

;; (append1) seems too complicated. It needs some work, but for now it works.

;

(defn append1 [sq elem]
  (if (seq elem)
    (lazy–cons sq elem)
    (concat sq (vector elem))))
;

;; It’s generally frowned on to produce side-effects in Clojure along the lines of what PG’s (conc1) function does, but if you were so inclined it would be done as:

;

(defn conc1 [sq elem]
  (dosync
   (if (seq? elem)
     (ref–set sq (lazy–cons @sq elem))
     (ref–set sq (concat @sq (vector elem))))))

(def x (ref '(4 5 6)))
@x
(conc1 x 4)
@x
;

;

(defn makelist [elem]
  (lazy–cons elem '()))
;

; pg. 47

;

(defn longer [x y]
  (let [cmp (fn [x y]
              (and (seq? x)
                   (or (nil? y)
                       (recur (rest x) (rest y)))))]
    (if (and (seq? x) (seq? y))
      (cmp x y)
      (> (count x) (count y)))))
;

;; The list-comprehension macro supplied by Clojure provides a powerful way to filter a sequence based on a :when or :while. Therefore an implementation of the filter function is trivial.

;

(defn filtr [f lst]
  (for [x lst :when (f x)]
    x))

(filtr even? '(1 2 3 4))
(filtr even? (range 100000))
(filtr seq? '(1 2 3 (4 5) 6 [7] 8 (9) "10"))
;

;; (group) could stand to be (a lot) more elegant

;

(defn group [source n]
  (if (zero? n) (pr "error: zero length"))
 
  (let [t (int (/ (count source) n))
        remainder (drop (* n t) source)]
    (lazy–cat
     (for [i (range t)]
       (take n (nthrest source (* i n))))
     (if (nil? remainder)
       '()
       (list remainder)))))

(group '(1 2 3 4 5 6 7) 4)
(group '(1 2 3 4 5 6 7) 400)
;

; pg. 49

;

(defn flatten [x]
  (if (seq? x)
    (apply concat (map flatten x))
    (list x)))
;

;; Clojure provides a powerful library for walking and editing trees functionally using a structure called a zipper. The library is fairly comprehensive, and its power is apparent in a few minutes playtime. There are a couple of missing features (outlined below), but overall it makes something like PG’s prune function a piece of cake.

;; One feature missing from the zip library is the ability to create a zip structure from any given type of seq-able data structure. That is, before you build a zipper you have to know the form of the data so that you can call one of (seq-zip), (vector-zip), or (xml-zip). This is a minor point overall, but making the prune more generic requires some work up front.

;

(defn zip–util [root]
  (if (seq? root)
    (zip/seq–zip root)
    (zip/vector–zip root)))
;

;; The prune function itself is taken alomst verbatim from the clojure zip examples except for a couple minor changes, one of which is to allow a filter function to decide the pruning as in “On Lisp” plus a call to (zip-util) to handle different types of structures. Another useful feature missing from the zip library is a predicate that can be used to check if a structure is already a zipper. As it stands trying to zip a zipper throws an exception and there was no clear way (that I could find) to perform such a check.

;

(defn prune [f tree]
  (loop [loc (zip–util tree)]
    (if (zip/end? loc)
      (zip/root loc)
      (recur
       (zip/next
        (if (f (zip/node loc))
          (zip/remove loc)
          loc))))))
;

;; PG’s (prune) function works on nodes only, but I thought it might be better to work on branches also. Of course, this breaks the ability to just send in something like (even?), but I think that is a minor tradeoff.

;

(defn node–filter [x]
  (if (zip/branch? x)
    nil
    (even? x)))

(def s '(1 2 (3 (4 5) 6) 7 8 (9)))
(def v [1 2 [3 [4 5] 6] 7 8 [9]])

(prune node–filter s)
(prune node–filter v)
;

; pg. 50

;; PG’s (before) is alomst a direct translation, except for one major difference: Clojure does not have default argument values. Therefore, one must always pass in a test function to get the same effect. I decided to drop the test function for now to simplify the function.

;

(defn before? [x y sq]
  (and sq
       (let [elem (first sq)]
         (if (= y elem)
           nil
           (if (= x elem)
             sq
             (recur x y (rest sq)))))))

(before? 'b 'c '(1 2 a b c))
(before? 1 'c '(1 2 a b c))
(before? 'a 1 '(1 2 a b c))


;; This is from CS-101
(defn member [x sq]
  (if (seq sq)
    (if (= x (first sq))
      sq
      (recur x (rest sq)))))

(defn after? [x y sq]
  (let [elem (before? y x sq)]
    (and elem
         (member x elem))))

(after? 'b 'c '(1 2 a b c))
(after? 'c 'a '(1 2 a b c))


(defn duplicate? [obj sq]
  (member obj (rest (member obj sq))))

(duplicate? 'a '(1 2 a b c a d))

;; Needs work
(defn split–if [f sq]
  [(for [x sq :when (f x)] x) (for [x sq :when (not (f x))] x)])

(split–if #(= % 5) '(1 2 3 4 5 6 7 8 9 10))
(split–if #(< % 5) '(1 2 3 4 5 6 7 8 9 10))
(split–if #(> % 500) '(1 2 3 4 5 6 7 8 9 10))
(split–if #(if (< % 7) true false) '(1 2 3 4 5 6 7 8 9 10))
;

;; Something to note: Clojure provides shorhand notation for lambda’s containing a single call of #(). This notation allows for the passing of multiple arguments each accessed via the % operator (e.g. %1 %2 etc…)

; pg. 52

;; Continuing with my abuse of the list-comprehension (only until it becomes second nature… any day now), the most function is pretty trivial.

;

(defn most [f sq]
    (let [wins (ref (first sq))
          mx (ref (f @wins))]
      (doall
       (for [x (rest sq) :when (> (f x) @mx)]
         [(dosync (ref–set wins x) (ref–set mx (f x)))]))
      (list @wins @mx)))

(most count '((1 2 3) (1 2)))
(most count '((1 2 3) (1 2 3 4)))
;

;; It’s important to note that the (for) had to be wrapped in a (doall) because the former generates a lazy sequence and will only supply the first argument, therefore you’re always going to see the first item in the sequence as the answer without the latter. It took me a while to track this down. :(

;

(defn best [f sq]
  (let [wins (ref (first sq))]
    (last
      (for [x (rest sq) :when (f x @wins)]
        (dosync (ref–set wins x))))))

(best > '(1 2 3 4 5))
(best > '(1 2 7 4 5))
(best > nil)
;

;; But of course, when Rich Hickey looked at my (best) function he gave me a virtual pat on the head and hit me with:

;

(defn best [f xs] (reduce #(if (f %1 %2) %1 %2) xs))
;

;; I remain humbled.

;; So of course, that means that (most) can more elegantly be written as:

;

(defn most [f xs] (reduce #(if (> (f %1) (f %2)) (list %1 (count %1)) (list %2 (count %2))) xs))
;

;; So PG goes on with this vein for a few more pages creating more utlity functions, some of which could be useful later on. PG’s main goal for Chapter 4 is to propone the virtues of Bottom-up programming, which I buy, but since my main goal is to learn Clojure and work out the long-dormant FP muscles, I only chose a handful of functions that furthered my goal.

;; Stay tuned for Chapter 5.

;-m

Related posts:

  1. On Lisp -> Clojure (Chapter 2 – redux)
  2. On Lisp -> Clojure (chapter 2)
  3. On Lisp -> Clojure (Chapter 5)
  4. On Lisp -> Clojure (Chapter 3)
  5. On Lisp -> Clojure: ProloG (pt. 1)

5 Comments, Comment or Ping

  1. David Siegel

    Shouldn’t (most) be:

    (defn most [f xs] (let [x (reduce #(if (> (f %1) (f %2)) %1 %2) xs)] [x (f x)]))

    Dec 14th, 2008

  2. Kunjan

    Hi, I am learning clojure. And your posts are very very helpful. Could you tell me why you use lazy to add to the list. I have seen a lot of lazy-cons and lazy-cat. What is the advantage of these?

    Thanks.

    Jul 22nd, 2009

  3. fogus

    @Kunjan,

    One thing to be aware of with these posts — they are hopelessly out of date. My use of lazy-cons is actually no longer legal Clojure code. At the time of this writing it was the way to cons an element onto the head of a sequence in a lazy way. By lazy I mean that the elements of the sequence are not calculated until accessed. Clojure is now mostly lazy and therefore it makes lazy-cons unnecessary. The more appropriate way to do this now is to use lazy-seq like so:

    (def foo (cons (do (println "hi there") 'x) '()))  ;; you will see "hi there" printed... non-lazy
foo   ;;  you will see (x)

(def foo (lazy-seq (cons (do (println "fff") 'x) '())))  ;; nothing is printed, until...
foo
;; now you will see "hi there" printed during the lookup of foo

    Hopefully, that clarifies matters.

    -m

    Jul 23rd, 2009

  4. Nevena

    flatten function won’t work. clojure.core 1.2 has the right one.

    Dec 3rd, 2010

  5. efraim

    Shouldn’t seq? be sequential? in the definition of flatten, since testing vectors for seq? returns false ?

    Nov 23rd, 2017

Reply to “On Lisp -> Clojure (Chapter 4)”