Lists, and functions that don't want them

Learning to operate on sequences of data is a continual challenge for me, and probably for other developers coming from an imperative background. I learned a little bit about working with lists yesterday, and I thought I would share it.

Trying to understand "partial" I asked for clarification on IRC. Specifically, I asked whether partial took the next value passed and added it as the rightmost element to the function, as it appeared in the following:

(map (partial + 2) '(1 2 3))
;; => (3 4 5)

When I was told that in fact, partial would take whatever parameters were supplied and add them to the right of the function that was partially declared, I tried removing the map:

((partial + 2) '(1 2 3))
;; => ClassCastException clojure.lang.PersistantList cannot be cast to java.lang.Number

I knew what to change to get it to work:

(apply (partial + 2) '(1 2 3))
;; => 8

I can't say that I understood right away why I needed 'apply' in this example. After some reflection, it seems pretty clear though. I was trying to invoke a function (+ 2 ….) on something. Using '+' with a collection does not work in Clojure.

Adding to a collection is done with 'cons' or 'conj'. I didn't want to put the number 2 into the collection, I wanted to operate on the items in the collection. That is where things like map and apply come in. They reach into the collection and allow you to operate on the members.

map works on each item independently. apply takes all of the items together.

(map (partial + 2) '(1 2 3))
;; => (3 4 5)

(apply (partial + 2) '(1 2 3))
;; => 8

Another function that operates on the members of a list individually is the filter function.

(filter (partial > 10) (range 20))
;; (0 1 2 3 4 5 6 7 8 9)

In the earlier examples the order didn't matter. '+' works the same left to right or right to left. When we use '>' it is important to remember that the values passed in to the function are passed to the right. The results of the filter look backwards if you don't think about how each partial function is applied:

(> 10 0) (> 10 1) .... (> 10 18) (> 10 19)

Do not think of 'partial' as being a place holder, but rather an indicator that more is to come at the end.

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: http://blog.fogus.me/2008/10/08/on-lisp-clojure-chapter-4/ 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)
    nil
    (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
     (filter
      (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.

On Lisp in Clojure ch 3

I am continuing to translate the examples from On Lisp by Paul Graham into Clojure. Today I am looking at chapter 3.

Section 3.1 Functional Design

Graham shows an example of a bad-reverse function, which modifies the list it was passed and then shows a good-reverse which returns a new list. I am not going to translate the bad example, because it is even uglier in Clojure, where you have to go out of your way to mutate things.

(defn good-reverse [lst]
  (loop [lst lst acc ()]
    (if (= () lst)
      acc
      (recur (rest lst) (cons (first lst) acc )))))

(good-reverse [1 2 3 4])

The next bunch of examples talk about different Lisp functions that alter the values of their parameters. None of the examples really make sense in Clojure. We will talk more about that in section 3.3.

The truncate example was interesting. I am not sure why you would have a function that returns multiple scalars in a list based language. Why not return a list? Clojure does not have a truncate function, but you can use quot and rem to get the same effect.

(defn split-decimal [n]
  {:quotient (quot n 1)  :remainder (rem n 1) :quotent-int (int n)})

(split-decimal 26.235)
(split-decimal 26.235M)

The split-decimal function returns a map that contains 2 floats and an int when called with a float, and 2 decimals and an int when called with a decimal.

Section 3.2 Imperative Outside-In

To square a number we can either use Java's Math class or Clojure's expt function. Java's Math.pow returns a double:

(defn fun [x]
  (list 'a (Math/pow (first x) 2)))

The exponent function in Clojure is stored in a library called math.numeric-tower. It will return an int when passed two ints, and return a double when one of the parameters is a double.

To get math.numeric tower, you need to add a dependency to the project.clj file. After the add, the dependency section in my project.clj looks like:

:dependencies [[org.clojure/clojure "1.3.0"]
               [org.clojure/math.numeric-tower "0.0.1"]]

You import this dependency by typing lein deps at the command line. (Assuming you are using Leiningen, and why wouldn't you?)

The functional version of his example is:

(use '[clojure.math.numeric-tower])

(defn fun [x]
  (list 'a (expt (first x) 2)))

I thought the imperative version of the function was extra awkward, probably because in CLISP let does not bind sequentially. In Clojure where let does bind sequentially, and mutating a variable takes extra work, it makes sense to assign your variables when you declare them. That is how I would do it in C# too, so I think it is a reasonable imperative idiom.

(defn imp [x]
  (let [y (first x) sqr (expt y 2)]
    (list 'a sqr)))

Section 3.3 Functional Interfaces

This section makes Clojure look like a better Lisp than Lisp. The first example shows a call to a function nconc, which joins lists together and then puts the result into the first list. His function manages to work in a good functional style because he makes a copy of the list he is passed in, and passes the copy to the nconc function. By default Clojure doesn't mutate data in place it returns a new copy.

(defn qualify [expr]
  (cons 'maybe expr))

(qualify '(this is true))

Using cons puts the 'maybe at the front of either a list or a vector. If you rewrite the function using into, the 'maybe will get added to the front of a list or the end of a vector.

(defn qualify [expr]
    (into expr '(maybe)))

(qualify ['this 'is 'true'])

The next example is of calling a function that increments a variable and returns the new value. Again, Clojure does by default what Graham is advocating. The difference is, in Clojure Graham's right way is also the easy way.

;; x is immutable
(let [x 0]
  (defn total [y]
    (+ x y)))

;; x is mutable
(let [x (atom 0)]
  (defn total [y]
    (swap! x #(+ % y))))

Clojure makes mutable state available when you need it, but mutability always takes more work than immutability. What's more, if you have something that you want to be mutable, you have to declare it as a mutable type (here we use an atom). When you are using values instead of variables, you have a guarantee that no other function can change that. You only have to worry about mutation in things that are mutable, which are either Clojure's mutable structures or mutable Java objects when doing interop.

Rather than go through the rest of the examples in this section, I will just take comfort that Clojure encourages me to do things in a way Graham is advocating.

Section 3.4 doesn't have any examples. It does give a good explanation of some benefits of functional programming though.

And that concludes chapter 3.

Looking Forward to Clojure West

This may sound like an advertisement, but hey, I am really looking forward to the conference.

Clojure West starts this Friday, March 16. Two days, 4 keynotes, 3 tracks with numerous sessions. There is going to be an Overtone jam session (with Heroku buying the beer), and we will get to see how they do Swarm Coding in Seattle.

I don't think I will be able to finish watching all of the videos from the last conference before this one starts. Two I recently watched that I really enjoyed were Kevin Lynagh discussing the advantages of ClojureScript over JavaScript from the 2011 Conj, and Chris Houser talking about Finger Trees (which look really useful despite the strange name) from the 2010 Conj. Both Lynagh and Houser are giving presentations at this conference as well.

There are still spaces available. It is also possible to get tickets for just Friday or just Saturday if that appeals to you. See you there?

On Lisp in Clojure ch 2 (2.7 - 2.10)

This is the fourth post translating the examples from chapter 2 On Lisp by Paul Graham into Clojure.

Section 2.7 Local Functions

;; apply function to all items in list
(map (fn [x] (+ 2 x))
     '(2 5 7 3))
;; or
(map #(+ 2 %)
     '(2 5 7 3))

The copy tree function didn't seem to do anything, the data looks the same to me after as it did before. But I think the point is that you can use map with a named function.

(map inc '(1 2 3))

The next example is a function that applies a function to each element of a list using a closure

(defn list+ [lst n]
  (map #(+ n %) lst))
(list+ '(1 2 3) 3)

The next set of eamples pertain to CLISP's labels function, which does not exist in Clojure. In Clojure let is evaluated sequentially so things that Graham says won't work in CLISP work in Clojure such as:

(let [my-inc (fn [x] (+ x 1))] (my-inc 3))
(let [x 10 y x] y)

The last example in this section is of mapping a recursive function to a list. I did my best to do a translation of this function into Clojure, but it doesn't actually work. It blows the stack. I have included it anyway, because it shows naming a function with the (fn name [params] form. The only recursion you want to use in Clojure is tail recursion, which is the subject of the next section. Generally, in Clojure though, you use sequences instead of recursion, but that discussion doesn't really fit here.

(defn count-instances [obj lists]
  (map (fn instances-in [lst]
    (if (seq? lst)
      (+ (if (= (first lst) obj) 1 0)
         (instances-in (rest lst))) 0)) lists))

Section 2.8 Tail-Recursion

Tail recursion in Clojure uses the recur form. The java virtual machine does not support tail call optimization. The recur form tells the Clojure compiler to compile the code to a loop to compensate.

I skipped the non-tail call recursive example of the our-length function.

(defn our-find-if [pred lst]
  (if (pred (first lst))
    (first lst) (recur pred (rest lst))))
(our-find-if even? [1 2 3 4])

The tail call version of our-length.

(defn our-length [lst]
  (loop [lst lst acc 0]
    (if (= () lst)
      acc
      (recur (rest lst) (+ acc 1) ))))
(our-length '(1 2 3 4))

This section ends with a discussion of optimization of Common Lisp. In Clojure you can get better performance using type hints. This tells the compiler which java type to use for a variable. Here is the Clojure optimized triangle function.

(defn triangle [^long n]
  (loop [c 0 n n]
    (if (zero? n)
    c
    (recur (+ n c) (- n 1)))))
(triangle 1000000)

The type hint gives an extra boost in this case. Normally the type hint makes reflection unnecessary. Here, we are specifying to use a java primitve (long) instead of a java object to hold the number. On my system, without the type hint the (triangle 1000000) call took 521 milliseconds. When I added the type hint, it went down to 11 milliseconds!

Section 2.9 covers compilation. Graham distinguishes between functions that are complied verses functions that are interpreted. In Clojure all functions are compiled.

Clojure does have a compile function, that was added in version 1.3. The documentation says that it is for compiling libraries, so it is not analgous to the compilation discussed in this section of On Lisp.

Section 2.10 does not contain any examples.

That's all for Chapter 2.

On Lisp in Clojure ch 2 (2.5 - 2.6)

This is my third post translating the examples from On Lisp by Paul Graham into Clojure.

Section 2.5 Scope

This section shows an example and describes how it would be evaluated with dynamic scope and lexical scope. Here is the example with Clojure syntax:

(let [y 7]
  (defn scope-test [x]
    (list x y)))

(let [y 5]
  (scope-test 3))

Like CLISP, Clojure uses lexical scope in this example, and like CLISP, there are ways to use dynamic scope. Amit Rathore covers scope in detail in Clojure in Action, but Graham doesn't cover in this part of his book, so I won't either.

Section 2.6 Closures

In the first example, the inner anonymous function gets the value of n from its enclosing function.

(defn list+ [lst n]
  (map (fn [x] (+ x n))
       lst))

(list+ '(1 2 3) 10)

Clojure's data structures are immutable by default, but the next example doesn't work without mutable state, so this version uses a Clojure atom.

;; lexically scoped counter
(let [counter (atom 0)]
  (defn new-id [] (swap! counter + 1))
  (defn reset-id [] (reset! counter 0 )))

(new-id)
(reset-id)

The next example defines a function that returns a function that adds a predetermined number.

(defn make-adder [n]
  (fn [x] (+ x n)))

(def add2 (make-adder 2))
(def add10 (make-adder 10))
(add2 5)
(add10 3)

The next example again creates an adder function, but an optional boolean parameter lets the caller change the amount that gets added with each call. Again we will use a Clojure atom for the mutable variable.

(defn make-adderb [n]
  (let [amt (atom n)]
    (fn [x & change ]
      (if change  (reset! amt x ))
      (+ x @amt))))

(def addx (make-adderb 1))

(addx 3)
(addx 100 true)
(addx 3)

The next example was out of order in the book. In the proper order, we create a make-dbms function that takes a collection of key value pairs and returns a list of functions that operate on that collection. In Clojure the logical data type to use is a map, rather than a list of lists. The coolness of this example, using a list of functions that operate on a collection provided by a closure work just fine with immutable state.

(defn make-dbms [db]
  (list
   (fn [key]
     (db key))
   (fn [key val]
     (assoc db key val))
   (fn [key]
     (dissoc db key))))

(def cities (make-dbms {'boston 'us, 'paris 'france}) )

cities is a list of functions that operate on the map of key value pairs. The comma in the collection is optional, I just think it makes the grouping more clear. Commas are whitespace in Clojure.

Here is how we call the functions:

((first cities) 'boston)
((second cities) 'london 'england)
((last cities) 'boston)

Even for a contrived example, we can't really get away with an immutable database. So here is the mutable version, again using atoms.

(defn make-mutable-dbms [db]
  (let [mdb (atom db)]
    (list
     (fn [key]
       (@mdb key))
     (fn [key val]
       (swap! mdb assoc key val))
     (fn [key]
       (swap! mdb dissoc key)))))

(def citiesx (make-mutable-dbms {'boston 'us, 'paris 'france}) )

((first citiesx) 'boston)
((second citiesx) 'london 'england)
((last citiesx) 'boston)

In a clear victory for hammock driven development, I realized that a map of functions made a lot more sense than a list of functions. This way, instead of calling first, second and last, we can call the functions by name, like so:

(defn make-dbms-map [db]
     (let [mdb (atom db)]
       {:select (fn [key] (@mdb key))
        :insert (fn [key val]
                  (swap! mdb assoc key val))
        :delete (fn [key]
                  (swap! mdb dissoc key))}))

(def citiesm (make-dbms-map {'boston 'us 'paris 'france}))
((:select citiesm) 'boston)
((:insert citiesm) 'london 'england)
((:delete citiesm) 'boston)

viva la clojure

Next time we will finish Chapter 2, covering local functions and tail recursion.