How can I provide a nice, convenient abstraction for tracking dirty list items?

Question

For fun and learning functional programming, I am developing a program in Clojure that performs an algorithmic composition using ideas from this music theory called Westergaard's Theory. It generates musical lines (where the line is just one character, consisting of a sequence of notes, each with a step and duration). It basically works as follows:

• Start with a line consisting of three notes (the selection is not important).
• Randomly perform one of several "operations" on this line. The operation is randomly selected from all pairs of adjacent notes that meet certain criteria (for each pair, the criterion depends only on the pair and does not depend on other notes in the string). It inserts 1 or more notes (depending on the operation) between the selected pair. Each operation has its own unique criteria.
• Continue to randomly perform these operations on the line until the line is needed.

The problem I am facing is that my implementation is rather slow and I suspect that it could be done faster. I am new to Clojure and functional programming in general (although I have experience with OO), so I hope that someone with more experience can indicate whether I think in the functional paradigm or not miss some FPs.

My current implementation is that each line is a vector containing maps. Each card has: a note and a: dur .: the note value is a keyword representing a musical note of type A4 or C # 3 .: dur value is a fraction representing the duration of a note (1 - a whole note, 1/4 - a quarter note etc.). So, for example, a line representing a scale of C starting with C3 would look like this:

[ {:note :C3 :dur 1} {:note :D3 :dur 1} {:note :E3 :dur 1} {:note :F3 :dur 1} {:note :G3 :dur 1} {:note :A4 :dur 1} {:note :B4 :dur 1} ] 

Let the problem of using a vector ( which is considered in another question ) be ignored. I want to focus on increasing the speed of determining which pairs of notes pass the criteria for a given operation.

The problem is that each operation must see which adjacent pairs of notes meet its criteria. This is currently O (n), where n is the row size (it just goes through the whole row and looks at each pair), which means that even if I fix the problem of using a vector, it will still be slow. However, a good test of the criterion is that it should only overestimate the notes whose neighbors have changed (since the criteria for each pair are independent of the other notes in the line). I'm not sure how I will track this in Clojure, so the algorithm will keep track of which pairs were dirty and which were clean, and only be able to re-evaluate pairs of notes that were dirty. Would it be nice, in terms of a paradigm, to track this using a map to attach a line and add metadata? For example, I would have such a structure:

 { :line [<the elements of the line>] :dirty [<indexes of notes that need to be re-checked>] :valid { operation1 [<indexes of notes that operation 1 can be performed on>] operation2 [<indexes of notes that operation 2 can be performed on>] ... } } 

How could I do something like this, but make it a beautiful abstraction? For example, I did not need to remember how each thing was structured every time I wanted to do something for this. Is there some kind of Clojure language feature that would be useful for abstracting this? Or is this not the best way to do this? I’m thinking about how easy it is to abstract implementation details like this in OO (for example, if I want to say that this note is now dirty, I can do something like .setDirty (index) instead of directly accessing the vector). I am sure there are ways to do this in Clojure / functional programming.

Does this sound like a decent way to track dirty notes? How can I encode this in Clojure to make it easier to use (by making a good abstraction, so I don’t need to remember how the map is structured).

Answer 1

Clojure protocols and records somewhat resemble object-oriented interfaces and classes. In this case, you can define a protocol for abstracting the main methods on the line:

 (defprotocol LineProtocol (extend [this]) (note-seq [this]) (length [this])) 

where extend creates a new line by applying a random operation to the random applicable note pair, length returns the number of notes in the line, and note-seq returns the sequence of notes in the line.

Then, by setting the start line, you can get the line of the desired length:

 (->> line (iterate extend) (drop-while #(< (length %) desired-length)) first note-seq) 

The abstraction of the implementation you have in mind may look like

 (defrecord Line [notes valid dirty] LineProtocol (extend [this] (->Line ...)) ;calc new line from this line state (length [this] (count notes)) (note-seq [this] (seq notes))) 

if notes is a vector. ( ->Line is the factory method generated by defrecord .)

Your implementation seems to me on the right track, although I think you need to evaluate all the dirty notes with each extend call.

Answer 2

I'm also interested in what @schaueho asks - do you really need to track dirty notes, or would it be enough to iteratively select the elements of a vector at random, examine them and the surrounding elements, check if the criteria are met, and if so, make changes to Otherwise, do nothing and move on until the line is at the desired length?

Assuming you need to track dirty notes, you really can store {:dirty true} as metadata for the note itself, for example:

 (with-meta {:note :C3 :dur 1} {:dirty true}) 

This would be like calling note.setDirty() in OOP.

Then determining whether the note is dirty is just as simple:

 (defn dirty? [note] (:dirty (meta note))) 

So your algorithm might look something like this:

 (loop [notes [{:note :C4 :dur 1} {:note :E4 :dur 1} {:note :G4 :dur 1}]] (if (>= (count notes) desired-length) notes (recur (let [note (rand-nth notes)] (if (dirty? note) notes (update-notes-and-include-dirty-metadata-on-affected-notes)))))) 

The question of how to accurately update an array at a specific index depends on your other question. I also thought about this, and I think that A. Malloy is probably on the right track with his fingers. If you are not dealing with extremely long melodies, I think the finger tree could do it well.