Musically Horizontal Monads
Sorry for the delay! My household has had a couple of chaotic days of everyone-being-very-very-sick and house guests and 4:30am airport drop-offs. But we’re back! This blog post got written in several parts over several days, so it might be a little disjointed. Apologies. In the last post we discussed a way of attaching durations to instantaneous musical events: just wrap them with a duration, stupid! Then we wrote a function which takes an event stream of stopping points, as well as an event stream of starting points 1 . It then spans each starting event until the next stop or start. The stops are there so that we can add silence if necessary. Having a function like around is cool because it means we can just emit starting and stopping events from whatever upstream process we might like, and it will automatically turn them into “rhythm.” And of course, that upstream process is welcome to derive the stop stream from the start stream (or vice versa), if you don’t want to have to think about it. Anyway, that’s all and good. But musicians have a lot of intellectual moment behind not thinking about music that way. Instead they usually just think of having durations intrinsically attached to notes — that is to say, they conceive of the note and the duration at the same time. Since we have an explicit desideratum here of making it easy to get good results, we ought to provide some more conventional ways of thinking about writing lines. Writing lines is usually done as “pick a note and a duration, then after that duration, pick another note and another duration. Rinse and repeat.” Of course, there’s some wiggle room where you can instead choose to not select a note and leave silence in its place. Depending on how functional-programming-pilled you are, this either sounds like a monoid or a monad. Let’s explore both ideas, starting with the monoid. A horizontal monoid seems like it ought to sequence one piece of music before another, in a temporal-sense. That is, should play , and then once is done, it should play . Recall that already has instances, but looking at the type, they necessarily can’t be the right thing: If you’re unfamiliar with the newtype, it lifts the and instances over the structure. That is, we’ve effectively derived the following instances: The clue that this is doing the wrong thing for our purposes is the constraint. If we were putting one after another in time , we’d never need to combine s, and thus we would have no need for a instance. Thus, this instance must be doing a point-wise zip of times. Which is all to say that this is no good to us. What we instead must do is build a wrapper type which provides the correct temporal-sequencing monoid. Let’s take a moment to pour over our primitives and see if any of them are feasible for actually making that happen. The relevant primitive happens to be : which long-time readers might recall has seen some action on this blog in the past. The idea is that we will run the first until the first occurrence of the , then use that in order to switch to the given continuation. So gives us the “do one thing after another” semantics we want (notice its lack of a constraint!) This happens to be most of the work done, now it’s just a matter of accumulating the rest of the bits we need: the actual notes we’re playing, the start points, and the stop points. Let’s package all of that up into a little datatype: A horizontal structure then is some sort of newtype over . As it happens, writing the monadic horizontal structure is going to be a little more informative at this point, since we can lift the monoidal version out directly. But we can immediately put to work! In the exact style of Yampa Switching , we will use the inuation monad , which allows us to bind over the in some function — in our case, this will be the that curries out of . This is already well-treaded territory on this blog, so you can go read the Yampa Switching post if you’re curious about the exact details here. As a first approximation, wrapping this up gives us the type: However, this is somewhat unsatisfactory. s are covariant in their output (here ), but is invariant in that parameter. Blinding moving forward with as written would mean we wouldn’t have an operation which in practice turns out to be quite a limitation indeed! Instead we can do a little bit of a Yoneda -style encoding, where we hold onto a function that maps from into the eventual result of the invariant parameter. Check this thing out: The idea is that we delay building up our until you hand us a way of mapping from into whatever type you eventually end up wanting. We usually use a trick like this to get a free functor , but here we’re using it to get a free bifunctor : The and instances also come already-paid-for, but we must write them out ourselves: This concludes our diversion into writing . Popping the stack: recall we’re still trying to write a monadic horizontal structure. Which we can now write out as (with being left intentionally unmotivated for the time being), getting all our relevant instances for free: Take a moment to appreciate how amazing GHC is here; each of those deriving vias is lifting an unrelated type through a polytype and through a , the latter of which doesn’t have most instances we’re actually intersted in! 2 Our primary introduction form for is , which acts as one for some amount of time, before rendering a continuation of type : Note that we issue a start event at time 0, and both a stop event and switch event at time . From this we can derive and , both of which use a constant value across their , differing only in what they return as a monadic continuation: And of course, the function we had to invent the machinery in order to provide: It’s probably worth taking a moment to discuss what exactly the hell is going on with all of this crazy yoneda continuation monad stuff. What does it buy us? Lets write a little motif: notice that this emits notes relative to its input. In somewhat-standard notation, looks like this 3 : using this triangle symbol to indicate the continuation. But now check this out. We can bind the result in order to build a musical sequence; looks like this: This happens to be the underlying machinery in Tymoczko’s work on sequences (chapter 4 of Tonality ), though it is not presented as such (and I suspect he didn’t have monads in mind when writing it.) Revitalized with a real connection to real musical ideas, we press on through the mires of abstract nonsense. The most pressing problem remaining is how do we eliminate ? By means of : which isn’t actually unsafe, but will be due to a few additions to our API in a second. But a nicer eliminator is , which as originally promised, calls on our behalf: Here we use and pass it a dummy continuation, since we know we’re never going to actually sample it past the duration of our . Then we take the output , sample only at the start points , and pass the stop points through unmolested. It can also be useful to turn a directly into an event stream, ignoring its spans: The final two mysteries remaining are the unmotivated parameter in , and why is unsafe. Recall that musicians often think about periods of silence, or rests. While we could model rests as a value in a -typed , this would get rather in the way of our nice combinators! In particular, nothing says we must interpret a as a discrete function; if it’s continuous, then the value would make sense. But if we’re exporting discrete function, then the s never actually show up and the s are unnecessary. So here’s the trick; this phantom type in corresponds to “are there any rests in this value?” We can use a to get ourselves a type-level value to play with: Our new combinator is the only thing that uses the parameter: Notice that sets a stop point at t=0, and doesn’t create any new start points. Furthermore, the actual value of type here is an value. It claims to be “impossible,” which we will enforce momentarily. Something peculiar here is that we only have a single type of kind , namely . How can we differentiate s that use from those that don’t? Our old friend the ST trick comes knocking, requiring that remain fully polymorphic: Now can give us a continuous function only when the doesn’t contain any s! Usage of makes no such guarantees, and thus will crash with the impossible error when used on a . Note that has no such compunctions; it samples its function only at the designated start points, which doesn’t provide. And since our semigroup/applicative instances are all temporally end-to-end, nothing can introduce a start point inside of a . We began all of this looking for a temporal monoid whose multiplication would glue horizontal structures end-to-end. We then switched over to making a monad that did the same thing, but we don’t need to give up on our dreams of monoids! In fact, is already the monoid we want, with a minor niggle in that it wants a semigroup/monoid over the continuation value. If we tie that to be everything falls out for free: I don’t actually think this type is worth using, since it means our introduction forms need to be lifted into this newtype. But it’s nice to know that we could do such a thing if we wanted to! That’s all I have to say about rhythm for now. I don’t consider this to be the last word, but it’s as far as I’ve figured anything out. I’ve been reading a ton of textbooks on the topic, and the author who seems to be the least confused about it is Peter Westergaard . His formulation is in terms of “if you want a listener to mentally parse a hierarchical structure out of your notes, what properties would make that parsing easy?” That’s a thing I’d like to explore further, but I’m on a publishing deadline here, so I can’t take too much time to do research in between blog posts. Next time we’ll discuss Tymoczko’s theory of harmony , which will dramatically power up our ability to make something that sounds like music. Until then! Writing that sentence out makes it clear that I got the arguments backwards. Oops! ↩︎ As a little aside, if you’re not 90%+ of your instances, you should start. Good places to look for opportunities involve the wrappers in and . ↩︎ In glorious SVG. Sorry for the shitty image quality in previous posts! ↩︎ Writing that sentence out makes it clear that I got the arguments backwards. Oops! ↩︎ As a little aside, if you’re not 90%+ of your instances, you should start. Good places to look for opportunities involve the wrappers in and . ↩︎ In glorious SVG. Sorry for the shitty image quality in previous posts! ↩︎
Web Development
Design
CSS
JavaScript
Entertainment
Writing
Gaming
Culture
AI
Media
Tutorial
Hardware
Ruby
Mobile
Programming
DevOps
Security
Music
Business
Java
Rust
Shell
