Why Euclidean rhythms and why Clojure? Well, Overtone! Having played with SuperCollider before and having developed a curiosity towards Clojure, Overtone seemed like a great segway into the latter.
For a while I have been wanting to experiment with quantifying, expressing and generating musically interesting rhythms. After a bit of research a recent paper turned up: The Euclidean Algorithm Generates Traditional Musical Rhythms. How cool is that? So I wanted to have my own implementation, as well as make a Clojure exercise out of it.
Euclidean rhythms, basically
A Euclidean rhythm is loosely defined as a sequence of beats and silences, where the beats are distributed as equidistantly as possible. With discrete and relatively short sequences this produces interestingly sounding results.
The rhythm is described as a function E(k, n) where k is the number of beats and n is the number of divisions (k < n). For example: E(3, 5) := [1 0 1 0 1].
The solution to ER works as follows, with examples:
Start with a sequence of n 1's and (k - n) 0's:
[1 1 1 0 0 0 0 0]
Remove as many same elements from the tail, and append them to as many other elements in the front as we can:
[[1 0] [1 0] [1 0] 0 0]
Repeat as many times as is sensible:
[[1 0 0] [1 0 0] [1 0]] [[1 0 0 1 0] [1 0 0]]
When repetitions no longer produce a new flat sequence, stop:
[1 0 0 1 0 1 0 0]
Using the powers of Clojure as we discover them, we can be a tiny bit more concise than Ruin & Wesen. The entire code is available as a Gist.
It feels like this should be a one-liner in Clojure, and maybe it can be. But for now we start modest (and maintain some early debuggability). This solution was discovered experimentally, better ones must exist out there so please do share.
The starting sequence is easy. This will generate a sequence like
[    ...].
(concat (repeat k ) (repeat (- n k) ))
Vectors or lists? So far I don't know! For the exercise it does not matter. Vectors are simpler to type, lists are what the core functions return. Seeing a mix of them seems normal.
We could start by popping elements off the end and so on, but let's not. A better way is to "zip" part of the "tail" with the head of the sequence. Then we need a way to get that "tail":
(defn split-seq [s] "Extract a tail of same elements: [1 1 0 0 0] -> [[1 1] [0 0 0]]" (let [l (last s)] (split-with #(not= l %) s)))
This says: walk the sequence as long as the element is not equal to the last one, then split. Now, the fun part: repeatedly zipping the sequence until we're nice and Euclidean.
I can has zip()?
Clojure has no direct equivalent of Python's
map will accept multiple sequences. If the elements are themselves sequences and the function is
concat, we have our zip:
tutorial.core> (map concat [  ] [  ]) ((1 4) (2 5) (3 6))
If the sequences are of different length,
map will stop at the end of the shortest one and ignore the rest (Python's
map, on the other hand, will pad the shorter sequences with
Nones). Lucky for us, this is exactly the behavior we need to satisfy step 2 of the solution. The length of the merged sequence will equal the number of elements that are being removed from the end.
Obviously, once our recombined list is down to 2 or 3 elements no new flat sequences will appear (if they do they will be shifted copies of each other -- prove that if you like). Using Clojure's multiple signatures let's define these as base cases:
(defn recombine ([a b] [a b]) ([a b c] [a b c])
I.e., with only 2 or 3 arguments just return the sequence.
Note that we pass the sequence as unpacked arguments instead of the sequence object itself. The only reason is that we can use the multiple signature mechanism for base cases instead of a far less elegant
Now, the real work:
([a b c & more] (let [s (concat [a b c] more) [head tail] (split-seq s) recombined (map concat head tail) r-len (count recombined)]
let's get a little procedural for a moment:
sis the reconstructed sequence in question
tailis the "same element" tail,
headis the rest of the sequence
recombinedis head and tail zipped together
r-lenis the length of the
There is a third base case: if the sequence becomes purely periodic (i.e.
[1 0] [1 0] [1 0] [1 0]). According to our definition of
split-with will return all tail and no head. Let's account for that:
(if (empty? head) s
Empty head! That does happen. Finally, the recursive step.
(apply recombine (concat recombined (drop r-len (drop-last r-len s))))))))
In other words, if a sequence is periodic just return it, otherwise construct a single pass of the recombined sequence (
recombined plus the middle portion of the original sequence,
r-len elements chopped off both ends) and recombine that.
Does it work?
tutorial.core> (recombine    ) [(1 0) (1 0)] tutorial.core> (recombine     ) [(1 0) (1 0) ]
Yes, it works.
(defn split-seq [s] "Extract a tail of same elements: [1 1 0 0 0] -> [[1 1] [0 0 0]]" (let [l (last s)] (split-with #(not= l %) s))) (defn recombine ([a b] [a b]) ([a b c] [a b c]) ([a b c & more] (let [s (concat [a b c] more) [head tail] (split-seq s) recombined (map concat head tail) r-len (count recombined)] (if (empty? head) ;; even pattern s (apply recombine (concat recombined (drop r-len (drop-last r-len s)))))))) (defn E [k n] (let [seed (concat (repeat k ) (repeat (- n k) ))] (flatten (apply recombine seed)))) tutorial.core> (E 3 5) (1 0 1 0 1) tutorial.core> (E 3 8) (1 0 0 1 0 0 1 0)