# Euclidean Rhythms and Haskell

Erich Grunewald Updated on ・8 min read

About a decade and a half ago, Godfried Toussaint published a paper (.pdf) with the winsome name The Euclidean Algorithm Generates Traditional Musical Rhythms. In it, he shows how the Euclidean algorithm (more on which in a minute) can describe complex rhythmical patterns from African, South American, Asian and European traditional music. He begins by inviting us to ask the question,

What do African rhythms, spallation neutron source (SNS) accelerators in nuclear physics, string theory (stringology) in computer science, and an ancient algorithm described by Euclid have in common?

Let us first consider the last of these. Euclid’s algorithm, which he described in the Elements (ca 300 BCE), is used to compute the greatest common divisor of two numbers. In programming terms, the greatest common divisor x of a and b is the highest value for which a modulo x == 0 and b modulo x == 0. For instance, the greatest common divisor of 9 and 21 is 3, because 3 is the highest value which divides both 9 and 21 without leaving a remainder. Euclid described his algorithm using repeated subtraction, but we can also do it by getting the remainder after integer division:

-- First, get the remainder after dividing the larger number by the smaller one.
Prelude> 21 rem 9
3
-- Then, divide the previous divisor by that remainder. Repeat until remainder is 0.
Prelude> 9 rem 3
0


When one gets a remainder of 0, look at the last divisor, which in this case is 3. That’s the greatest common divisor. Here’s another example, this time of 1071 and 462:

Prelude> 1071 rem 462
147
Prelude> 462 rem 147
21
Prelude> 147 rem 21
0


So the greatest common divisor of 1071 and 462 is 21.

So far so good. But how does this relate to musical rhythms? First observe that one common way of representing rhythms is as a sequence of xs and .s, where an x is a hit and a . is a rest. (This is of course a simplification, but many if not most rhythms do recognisably follow patterns described in this way.) For example, the Afro-Cuban tresillo rhythm can be written as [x . . x . . x .].

The tresillo has 3 hits (or pulses) over 8 time steps (or points). Looking at the rhythm, one can see that the 3 pulses are quite evenly distributed over the 8 points. As it turns out, we can build an algorithm very similar to the Euclidean algorithm that distributes k pulses as evenly as possible over n points. Here is how my version (which is a little bit different from that used by Toussaint) of that algorithm works.

Say we want to generate a rhythm of k = 7 pulses over n = 16 points. Following the Euclidean algorithm, we know that 16 = 2 * 7 + 2, so we start off with 7 groups of size 2 and a remainder of 2:

[x .] [x .] [x .] [x .] [x .] [x .] [x .] [.] [.] (1)

On this initial step only, we put the 7 pulses at the head of each of the 7 groups. The remainder will be either pulses (xs) or rests (.s) as needed.

The task now is to distribute the remainder (the final 2 rests) evenly over these 7 groups. Given that 7 = 3 * 2 + 1, we see that we can divide those 7 groups into 2 groups of length 3 and a remainder of 1 (shown in curly braces):

{ [x .] [x .] [x .] } { [x .] [x .] [x .] } { [x .] } [.] [.] (2)

Note that here we are not grouping individual xs or .s, but the groups themselves – the algorithm is recursive. Placing the remainders at the tail of each of these groups, we get

{ [x .] [x .] [x .] [.] } { [x .] [x .] [x .] [.] } { [x .] } (3)

The new remainder is now length 1. When we have reached a remainder of 1 or 0, we are done. Concatenating the sequences, we get

[x . x . x . . x . x . x . . x .] (4)

– a Euclidean rhythm! Specifically, this is the Euclidean rhythm of 7 pulses over 16 points. Toussaint, in his paper, introduces a new notation for describing these rhythms: E(k, n). We have just generated the Euclidean rhythm E(7, 16), which, as it turns out, so Toussaint reports, is found in traditional Brazilian music.

Let’s take another example. Let us calculate the Euclidean rhythm E(3, 8):

1. [x .] [x .] [x .] [.] [.] (3 groups of size 2 plus remainder of 2, for 8 = 2 * 3 + 2)
2. { [x .] } { [x .] } { [x .] } [.] [.] (2 groups of size 1 plus remainder of 1, for 3 = 1 * 2 + 1)
3. { [x .] [.] } { [x .] [.] } { [x .] } (distributing the values over the new groups)
4. [x . . x . . x .] (concatenating the result, as we have a remainder of 1)

The observant reader will recognise this as the rhythm mentioned above, namely the Afro-Cuban tresillo. Toussaint goes on to enumerate a large number of Euclidean rhythms that occur in traditional music, including

• E(2, 3) = [x . x], “a common Afro-Cuban drum pattern”.
• E(3,4) = [x . x x], “the archetypal pattern of the Cumbia from Colombia, as well as a Calypso rhythm from Trinidad. It is also a thirteenth century Persian rhythm called Khalif-e-saghil, as well as the trochoid choreic rhythmic pattern of ancient Greece.”
• E(4, 9) = [x . x . x . x . .], “the Aksak rhythm of Turkey”.
• E(5, 8) = [x . x x . x x .], “the Cuban cinquillo pattern. When it is started on the second onset it is also the Spanish Tango and a thirteenth century Persian rhythm, the Al-saghilal-sani.”
• E(5, 16) = [x . . x . . x . . x . . x . . . .], “the Bossa-Nova rhythm necklace of Brazil”. (A rhythm necklace is a rhythm considered independently of where it is started. For instance, [x . x] and [x x .] are different rhythms but part of the same rhythm necklace.)
• E(7,16) = [x . . x . x . x . . x . x . x .], “a Samba rhythm necklace from Brazil. When E(7, 16) is started on the fifth onset it is a clapping pattern from Ghana.”
• E(11, 24) = [x . . x . x . x . x . x . . x . x . x . x . x .], “a rhythm necklace of the Aka Pygmies of Central Africa”.

And so on and so forth … Toussaint’s examples are mostly limited to Africa, South America, western Asia and Europe, but it is unclear whether that is because Euclidean rhythms are only found in these regions, or because Toussaint simply did not have any data for other regions. In any case, it’s a powerful way to generate complex, interesting rhythms, which is evident in the fact that it has since showed up in live-coding DSLs, software sequencers and many hardware modules.

We can also represent these rhythms in a more compact way, using the distances between each pulse. For instance, the Aksak rhythm [x . x . x . x . .] could be represented as 2223, and the tresillo [x . . x . . x .] as 332. This is a much more convenient way of representing rhythms in code.

As I have been exploring the Haskell music-making library Euterpea recently, I had a go at writing a function that generates Euclidean rhythms in this format. The result is as follows.

{-| Takes number of pulses k and number of points n and returns a Euclidean
rhythm represented as a list of k distances.
-}
euclid :: Int -> Int -> [Int]
euclid k n =
let
quot = n div k
rem = n mod k

-- We want k pulses, hence we will have k distances. The distances, if
-- they are to be as evenly distributed as possible, need to be at least
-- as high as the quotient. E.g. for E(3,8) we get 222 here.
base = replicate k quot

-- We want n points, so the total sum of all distances should be n.
-- Hence we need n - sum base additional distance units. We'll
-- distribute these evenly over the first n - sum base pulses.
-- Continuing the example, 8 - (2 + 2 + 2) = 2, giving us 332. These
-- are the final distances that we want to return, only now they are not
-- evenly distributed. To achieve that end, we call distribEvenly.
distances = zipWith (+) base (replicate rem 1 ++ replicate (k - rem) 0)
in
distribEvenly distances


What this function does is set up the constituent elements – the distances we’ll want in our final result – and then call the distribEvenly function to space them out evenly. The rhythm 332 is of course already evenly distributed (332 being rotations of 323 and 233), but a sequence such as 22211, which is what distances would be for the cinquillo pattern, is not. Let’s look at distribEvenly.

{-| @distribEvenly@ takes a list of ordered numbers (of two different values
only) and returns them evenly distributed over the indices. For instance,
[2,2,2,1,1] or [1,1,2,2,2] returns [2,1,2,1,2].
-}
distribEvenly :: (Num a, Ord a) => [a] -> [a]
distribEvenly xs =
let
maxVal = foldl max 0 xs -- maximum value from the list

-- Split the list into two, one containing all the higher values
-- (initAcc) and one containing the lower values (remainder).
(remainder, initAcc) = span (< maxVal) $sort xs in -- Now we nest each of the high values into its own list. We then call -- distribEvenly', which will intersperse the lower numbers in these -- lists. For the example above, we would call it with -- [[2],[2],[2]] and [1,1]. distribEvenly' (map pure initAcc) remainder {-| @distribEvenly'@ takes a list of lists of something (the accumulator) and a list of something (the remainder) and returns the accumulator with the remainder evenly distributed within it. For example, calling distribEvenly' [[2],[2],[2]] [1,1] returns [2,1,2,1,2]. -} distribEvenly' :: [[a]] -> [a] -> [a] -- If the remainder is empty, concatenate and return the accumulator. distribEvenly' acc [] = concat acc -- If the remainder has only one element, tack it onto the end of the -- concatenated accumulator and return the result. distribEvenly' acc (rem:[]) = concat acc ++ [rem] distribEvenly' acc rem = let -- Distribute all the remainder values over the accumulator (as far as -- possible). For the example above, we'd get [[2,1], [2,1]] (as zip -- always creates a list of the length of the shorter input list). newAcc = map (\(xs, y) -> xs ++ [y])$ zip acc rem

-- Calculate what's left of the old remainder (in our example, []).
remnantOfOldRem = drop (length newAcc) rem
-- Calculate the new, higher-level remainder (in our example, [2]).
newRem = drop (length newAcc) acc
in
if length remnantOfOldRem > 1
-- If there's more than 1 element left of the old remainder, we'll keep
-- going with that one, distributing it's values in the accumulator.
then distribEvenly' newAcc remnantOfOldRem
-- If not, we'll do the same thing recursively at a higher level. In
-- other words, if there are any odd subdivisions, we need to distribute
-- those evenly, too.
else concat \$ distribEvenly' (map pure newAcc) newRem ++ [remnantOfOldRem]


(Needless to say, I welcome any suggestions for how to improve this code.)

Having been too lazy to write any unit tests, we will have to use our actual muscles to test it:

Prelude> euclid 7 16
[3,2,2,3,2,2,2]
Prelude> euclid 3 8
[3,3,2]
Prelude> euclid 5 8
[2,1,2,1,2]
Prelude> euclid 11 24
[3,2,2,2,2,3,2,2,2,2,2]


I invite the curious reader to read the original paper, which is really quite simple and engagingly written.

The idea of evenly distributing k somethings over n spaces can be applied to other areas of music theory, too. For instance, E(7, 12) = [2,1,2,2,1,2,2] describes the intervals of the common minor scale of Western music, and started on the 3rd onset it is the common major scale. And all of these patterns are described, remember, with only two relatively prime integers.

Cover image: Perspectiva Corporum Regularium by Jost Amman, licensed under CC0 1.0.

Posted on by:

### Erich Grunewald

First-class second-rate coder.