How can I represent a line of music notes in a way that allows fast insertion at any index?

Question

For "fun", and to learn functional programming, I'm developing a program in Clojure that does algorithmic composition using ideas from this theory of music called "Westergaardian Theory". It generates lines of music (where a line is just a single staff consisting of a sequence of notes, each with pitches and durations). It basically works like this:

1. Start with a line consisting of three notes (the specifics of how these are chosen are not important).
2. Randomly perform one of several "operations" on this line. The operation picks randomly from all pairs of adjacent notes that meet a certain criteria (for each pair, the criteria only depends on the pair and is independent of the other notes in the line). It inserts 1 or several notes (depending on the operation) between the chosen pair. Each operation has its own unique criteria.
3. Continue randomly performing these operations on the line until the line is the desired length.

The issue I've run into is that my implementation of this is quite slow, and I suspect it could be made faster. I'm new to Clojure and functional programming in general (though I'm experienced with OO), so I'm hoping someone with more experience can point out if I'm not thinking in a functional paradigm or missing out on some FP technique.

My current implementation is that each line is a vector containing maps. Each map has a :note and a :dur. :note's value is a keyword representing a musical note like :A4 or :C#3. :dur's value is a fraction, representing the duration of the note (1 is a whole note, 1/4 is a quarter note, etc...). So, for example, a line representing the C major scale starting on 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}
]

This is a problematic representation because there's not really a quick way to insert into an arbitrary index of a vector. But insertion is the most frequently performed operation on these lines. My current terrible function for inserting notes into a line basically splits the vector using subvec at the point of insertion, uses conj to join the first part + notes + last part, then uses flatten and vec to make them all be in a one-dimensional vector. For example if I want to insert C3 and D3 into the the C major scale at index 3 (where the F3 is), it would do this (I'll use the note name in place of the :note and :dur maps):

1. (conj [C3 D3 E3] [C3 D3] [F3 G3 A4 B4]), which creates [C3 D3 E3 [C3 D3] [F3 G3 A4 B4]]
2. (vec (flatten previous-vector)) which gives [C3 D3 E3 C3 D3 F3 G3 A4 B4]

The run time of that is O(n), AFAIK.

I'm looking for a way to make this insertion faster. I've searched for information on Clojure data structures that have fast insertion but haven't found anything that would work. I found "finger trees" but they only allow fast insertion at the start or end of the list.

Edit: I split this into two questions. The other part is here.

Answer 1

One thing you have missed is that, in theory anyway, finger trees do give fast insertion at any index. They only directly allow you to insert at either end, but they also provide fast splitting and fast concatenation, so a fast insert-anywhere function can be framed as "split into two sequences, append to one of them, and then concat them together again".

I say "theoretically" because finger trees rely on constant-time memory access, but they generate many more cache misses than a simpler vector, and often don't perform as well as you'd expect. Finger trees are fun to play with, but aren't commonly used in clojure and I wouldn't really recommend using them for real.

One possibility is to just continue using the slow operations. If your vectors are never very long, and performance isn't crucial, then the O(n) insertion operation just won't matter very much.

If that's no good, there is a solution that has the O(log(n)) insertion that you want, although it's not a lot of fun. The answer is...to simulate mutable pointers! This is an approach that often works: if pointers were mutable, you could just have a linked list, where each cell knows its two neighbors, and update them as needed when inserting. But you can't here, because circular references aren't great for functional data. But, you can add a level of indirection: give each cell a unique "label", and have it only store the labels of its neighbors. Then you have no circular references, and you can make local updates cheaply. Here's an example of the layout I'm describing, your C-major scale:

{:cell-data {0 {:left nil :right 1, :note :C3 :dur 1}
             1 {:left 0 :right 2, :note :D3 :dur 1}
             2 {:left 1 :right 3, :note :E3 :dur 1}
             3 {:left 2 :right 4, :note :F3 :dur 1}
             4 {:left 3 :right 5, :note :G3 :dur 1}
             5 {:left 4 :right 6, :note :A4 :dur 1}
             6 {:left 5 :right nil, :note :B4 :dur 1}}
 :first-node 0, :last-node 6}

Here the numbers are sequential, but you can see how you could add a node in between 5 and 6, by creating a new node with {:left 5 :right 6}, and changing the :right of node 5, and the :left of node 6.

This organization is kinda a hassle, but it does meet your needs.