Patterns in Haskell

I’ve been trying to make music with Haskell for a little while now.  One thing about Haskell is that its strict typing forces you to think a lot about how you represent things.

I wanted to support two things in my musical pattern representation, firstly polyphony (more than one sound being triggered at the same time) and secondly recursive structure. In the west we often think of rhythm in quite `flat’ terms – a 2d pattern like this:

fruity

Of course that’s a pretty useful techno interface, allows for polyphony, and could be represented in haskell using a straightforward list of lists.  However this 2D structure is only really suitable for making music with fixed timed signatures, most notably 4/4.

Time: you're doing it completely wrong
Time: you're doing it completely wrong

Enter Bernard Bel (pictured right).  His BP2 software represents music in a manner inspired by Indian classical music.  His 2001 paper Rationalising musical time has all the details and is a great read, formalising a quite beautiful way of thinking about time. As part of that it defines an elegant pattern syntax that allows patterns to be embedded inside patterns of differing time signatures.

Here’s my first attempt at representing analogous structures in Haskell.  Straightforwardly, a musical event is either a sound (represented by some string) or some silence:

data Event = Sound String
           | Silence

A musical structure is either an event, a cycle of structures, or a polymetry of structures:

data Structure = Atom Event
               | Cycle [Structure]
               | Polymetry [Structure]

A cycle allows us to sequence structures one after another, and a polymetry allows us to represent several structures occuring over the same period of time.  If the structures within a Polymetry have different durations, then they are ‘stretched’ until they are the same length (equal to the lowest common multiple of their lengths). I’ve written something in parsec that parses Bel’s notation into the Structure datatype.

The problem with the above representation is that it gets unwieldy with complex rhythmic structures.  The whole point of generative music is being able to make very long patterns out of much shorter rulesets.  However with this representation, to find the 10,000th event you’d have to calculate the 9,999 events preceeding it.  This becomes a particular problem when modifying these structures as part of a live coded musical improvisation.

So I instead came up with this representation:

data Pattern a = Pattern {at :: Int -> [a], period :: Int}
type SoundPattern = Pattern String

Instead of explicitly representing a recursive structure, I’m now hiding everything inside a function mapping from integers to a list.  You pass the function the current position in the pattern (e.g. the current ‘beat’, and get back the list of events at that position.  For certain operations you still need to know the period (length) of the repeating pattern, so that’s in the datatype constructor too.

What kind of operations can I do to these patterns?  Here’s one that simply shifts events backwards in time:

(<~) :: Pattern a -> Int -> Pattern a
(<~) p steps = Pattern (\n -> at p (n + steps)) (period p)

And in the other direction:

(~>) :: Pattern a -> Int -> Pattern a
(~>) p n = (<~) p (-n)

Here’s a higher order one that applies an operation conditional on the time value (while preserving the period of the original):

when :: (Int -> Bool) -> (Pattern a -> Pattern a) -> Pattern a -> Pattern a
when pred f p = Pattern l (period p)
where l n = at (if (pred n) then (f p) else p)  n

Making this possible …

when (\n -> n `mod` 8 > 3) (<~ 2) p

… which shifts the pattern back in time two steps, but only affects every other group of 4 steps.

This is probably fairly humdrum stuff, but quite fascinating to me as someone relatively new to both haskell and functional programming. Being able to pile functions on top of functions in this way lets me compose complex patterns out of simple parts, and I only ever have to deal with the simple parts in memory, not the complex patterns. Great! Thanks to the parameterisation of the Pattern datatype, I can also use patterns for different aspects of a rhythm, my recent screencasts [1,2] showing concurrent patterning of samples, vowel formant filtering, sample playback speed and a comb filter.

I’ve also been looking at making the Pattern a Monad (my first ever monad instance, woo!):

instance Monad Pattern where
    return x = loop $ [x]
    (Pattern l len) >>= f = Pattern l' (lcm len len')
        where l' n = at (combine $ map f (l n)) n
              (Pattern _ len') = f undefined

Where ‘combine’ is another function not shown that which merges patterns together. The problem I’m having with this is that functions of type a -> Pattern a for use with >>= can’t do that much, not being able to consider any pattern context, and not being able to return a different period depending on the input (otherwise that ‘undefined’ value would bite). This is about the most useful thing I can come up with, which ‘masks’ events every other time measure:

mask :: (a -> Pattern a)
 mask x = Pattern (\n -> if n `mod` 2 == 0
                         then [x]
                         else []
                   ) 2

Maybe I should be thinking of what I could do with more general functions of type (a -> Pattern b) instead. I guess I’m just getting a better handle on what monads are really for…

Monads aside I guess my Pattern representation would really become unstuck with patterns that have a lot of interdependencies. For example if every event depended on the event preceding it then you’d have to recalculate the whole pattern all the time. Hmm.

Well that was quite an extended haskell wibble. If by some strange chance you’ve read this far I’d love to hear your thoughts and especially advice!

11 thoughts on “Patterns in Haskell

  1. Alex,

    have you ever looked at JMSL?

    http://www.algomusic.com/jmsl/tutorial/index.html

    It, and its precurser, HMSL (Hierarchical Music Specification Language) tackle a some of the ideas you’re working with. It’s clear you’re having a lot of fun leaning functional programming and digging around in haskell, and I think that’s a great way to go. You might want to take a look at some of the ideas in HMSL/JMSL just to see how other people worked through some of this stuff in a different world.

    HMSL was written in Forth! It was the first language I really did any music with. dupswapdrop. Most of Larry Polansky’s music is HMSL/JMSL-based. Plus JMSL now makes it easy to crank out traditionally notated scores, which can be really nice.

    douglas

  2. Hey Douglas!

    No I haven’t, I will take a look though, cheers for the tip. I’ve been meaning to have a proper look at supercollider’s pattern library too, which I think is based on HMSL.

  3. It looks to me like Pattern isn’t *quite* a Monad. Usually it’s easier to define fmap, join, and return, and use the boilerplate monad instance:

    fmapPattern :: (a -> b) -> Pattern a -> Pattern b
    returnPattern :: a -> Pattern a
    joinPattern :: Pattern (Pattern a) -> Pattern a

    instance Functor Pattern where fmap = fmapPattern
    instance Monad Pattern where
    return = returnPattern
    m >>= f = joinPattern (fmap f m)

    I think it’s likely that Pattern is only an applicative functor, and not a monad:

    instance Applicative Pattern where
    pure x = loop [x]
    (Pattern fs pf) (Pattern xs px) = Pattern fxs (pf*px) where
    fxs n = fs n $ xs n

  4. Sorry about the formatting, the operator used in Applicative is <*>. Also, I realized that “fxs” doesn’t quite typecheck, but if you replace ($) with <*>, you get a definition that does!

    Also, you may want to look at the Reactive library; I am seeing some striking similarities between what you are defining and that library. There’s a paper about the library here: http://conal.net/papers/push-pull-frp/

  5. A function of type
    a -> Pattern b
    doesn’t really make sense, since it would consume anything, and produce a pattern of some other, totally unrelated type. Also not everything needs to be made into a monad (since not everything is one), you can combine things in other ways too. That said, good luck and have fun using Haskell to make music :) This might be of interest to you: http://www.haskell.org/haskore/

  6. Thanks for looking into my code Ryan and leadnose. So you mean my monad instance doesn’t conform to the monad laws? Well at least I’ve learned a lot through trying to make it one.

    I did make Pattern an Applicative instance on the way to the Monad instance:

    > instance Applicative Pattern where
    >     pure a = loop $ [a]
    >     pf@(Pattern _ n) <*> pa@(Pattern _ n') = Pattern l (lcm n n')
    >         where l n = map (\(a, b) -> (a b)) $ zip (cycle (at pf n)) (at pa n)

    … although at the moment I’m not sure what that buys me. Much to read!

    I’ll have a go at Conal’s paper for sure Ryan, interesting that what I’m trying to do is somehow related to FRP, I had no idea.

    Good point about a -> Pattern b being useless leadnose. I was thinking of functions from some particular type to some other particular type, rather than to the same type, but of course they’d have a less general signature than that. After too long programming perl, this is all still coming together in my head…

  7. Hi Alex. Your patterns remind me of FRP also. The two representations are akin to syntax (algebraic data-type) & semantics. I think you’ve done what I often like to do as well, which is to program directly with denotations rather than data structures.

    There is a hazard in using functions as your representation that took me many years to grok. Ironically, functional programming is biased against functions and in favor of data structures, in that data structures are automatically memoized, while functions are not.

    Typically FRP uses continuous time, unlike your choice of Int, but that choice is not fundamental. BTW, did you consider continuous “time” here? Whether time or space, continuous is usually more composable than discrete. See brief related remarks at http://conal.net/blog/posts/early-inspirations-and-new-directions-in-functional-reactive-programming/ .

  8. I posted a long response (which ends with a suitable Monad instance for Pattern) here: http://ryani.livejournal.com/19471.html

    I don’t like your applicative instance (it is similar to the applicative instance for zip-lists); I think the applicative instance for regular lists makes more sense. The difference is that [(+1),(+2)] [3,4], for regular lists is [4,5,5,6], but for ziplists is [4,6]. Still, I can see how you might want to go that direction.

    However, you also give special treatment to the “f” argument; if it’s short, the resulting list gets cycled, but if the “x” argument is short, it doesn’t. I am pretty sure that violates one of the applicative functor laws. (f <*> pure x = pure ($x) <*> f).

  9. Much food for thought, thanks Conal and Ryan.

    Ints made sense to me as a representation of ‘score time’. A series of slots where things can go. To get ‘performance time’ e.g. swing, I add floating point offsets to that. I have to think more on this though, looking forward to learning more about FRP.

    I went for what you point out is ziplist-like behaviour so I could effect particular ‘levels’ in a polymetric pattern. I think that should probably be done in a more explicit way though. I’ll respond to your blog post properly soon Ryan.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>