[Cs254f11] elegance of functional programming

[Lee Spector]

Genetic Programmers,

I was thinking about some music-related programming examples both because a couple of you are working on music and because musical manipulation of sequences of numbers (which can be pitches or rhythms etc) provides nice examples in general, and one function that I thought would be handy is an "intervals" function that returns the differences between successive notes. (For the non-musicians, the most important thing about a melody is the intervals, not the notes themselves; if you use the same intervals but start on a different first note then it'll still sound like the same melody, just in a different key.)

In other words, if you have something like:

(def mynotes [60 62 64 65 67 69 71 72 71 69 67 65 63 62 60])

then you'd like (intervals mynotes) to return:

(2 2 1 2 2 2 1 -1 -2 -2 -2 -2 -1 -2)

My first thought (but not my best one -- that's at the bottom!) was to do this using the standard Lisp "recurse down a list" pattern. We'd first ask if we were given less than 2 notes, and if so then return an empty list (since there are no intervals if you don't have at least 2 notes). If that wasn't the case then we'd return the result of tacking the first interval -- which is the second note minus the first note -- onto the result of calling intervals (recursively) on all of the notes except the first. Here's what that looks like:

(defn intervals
  [notes]
  (if (< (count notes) 2)
    ()
    (cons (- (second notes) (first notes))
          (intervals (rest notes)))))

It works fine, although this kind of recursion is frowned upon in Clojure, because Clojure (unlike some other Lisps) can't optimize away the recursion and so this will run out of memory for recursive calls if you give it a really big list (although it'd have to be very big before you failed).

So here's a version that uses a similar strategy except that it uses Clojure's loop/recur structure instead of ordinary recursion.

(defn intervals
  [notes]
  (loop [remaining notes
         result ()]
    (if (< (count remaining) 2)
      result
      (recur (rest remaining)
             (concat result 
                     (list (- (second remaining) 
                              (first remaining))))))))

Also works, but pretty messy.

Then I remembered that Clojure has a fancy "partition" function that can do lots of things (check its docs), including, if given the right arguments, giving us overlapping pairs of a sequence: the first and the second, the second and the third, the third and the fourth, etc. If I do this then I can map a function down those pairs that subtracts the first element from the second element, producing a list of the intervals:

(defn intervals
  [notes]
  (map (fn [[n1 n2]] (- n2 n1))
       (partition 2 1 notes)))

Better, yes? But then I smacked my forehead (not literally, in fact I was driving at the time and that would have been dangerous :-), and remembered that, as we mentioned in class yesterday, when you map down more than one list it stops as soon as the shortest one is exhausted. Voila:

(defn intervals
  [notes]
  (map - (rest notes) notes))

Nifty!

 -Lee


--
Lee Spector, Professor of Computer Science
Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector at hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438