The Unthingable

Euclidean rhythm generator in Haskell

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]