So, Haskell! After a few days of astonished dabbling, the Euclidean Rhythm exercise had to be repeated. Again, this is beginner level code and we rely entirely on type inference.
The function breakdown is a little different this time. Two helper functions:
ezip: a hybrid of zip and outer join, takes two lists of different lengths and concatenates their elements pairwise;efold: repeatedly applies the tail end of the sequence under construction to the head, using ezip, until either there are 3 or fewer subpatterns or the pattern is cyclic.
The entire solution:
euclidean k n = concat . efold $
(replicate k [1]) ++ (replicate (n - k) [0])
ezip x [] = x
ezip [] x = x
ezip (x:xs) (y:ys) = (x ++ y) : ezip xs ys
efold xs
| length xs <= 3 = xs
| a == [] = xs
| otherwise = efold $ ezip a b
where (a, b) = partition (/= last xs) xs
And that's it! Notice how concise yet readable this is compared to an already terse Clojure version.
Similar to the Clojure example, it is not immediately obvious why a == [] is a terminal case. Empty a really means this: partition was unable to find different elements because they are identical -- the pattern is cyclic. A less efficient but more explicit way to write this would have been with a allSame function:
euclidean' k n = concat . efold' $
(replicate k [1]) ++ (replicate (n - k) [0])
ezip' (x, []) = x
ezip' ([], x) = x
ezip' ((x:xs), (y:ys)) = (x ++ y) : ezip' (xs, ys)
allSame [] = True
allSame [x] = True
allSame (x:y:xs) = (x == y) && allSame (y:xs)
efold' xs
| length xs <= 3 = xs
| allSame xs = xs
| otherwise = efold' . ezip' $ partition (/= last xs) xs
And, a test:
*Play> euclidean 3 5
[1,0,1,0,1]
*Play> euclidean 3 8
[1,0,0,1,0,0,1,0]
My first Clojure function is a Euclidean Rhythm generator, and I felt like sharing it. I found a post doing a similar thing, albeit in LISP. They called it "exploratory programming", and so will I.
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:
-
Remove as many same elements from the tail, and append them to as many other elements in the front as we can:
-
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:
Implementation
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 [[1] [1] [0] [0] ...].
(concat (repeat k [1]) (repeat (- n k) [0]))
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 zip, but 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] [2] [3]] [[4] [5] [6]])
((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.
Let's recurse!
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 if statement.
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:
s is the reconstructed sequence in questiontail is the "same element" tail, head is the rest of the sequencerecombined is head and tail zipped togetherr-len is the length of the recombined part
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-seq, split-with will return all tail and no head. Let's account for that:
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] [1] [0] [0])
[(1 0) (1 0)]
tutorial.core> (recombine [1] [1] [1] [0] [0])
[(1 0) (1 0) [1]]
Yes, it works.
Wrap up
(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 [1]) (repeat (- n k) [0]))]
(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)
Voila.