Shuffling my playlist with Perl and quantum mechanics

Introduction

There are handful of reasons one might want to set up their own radio. A common playlist for a group of friends is one of them. Another one is having a fine-grained control over the logic behind the shuffling mechanism. Thankfully, setting up your own radio is easy now with Audio::StreamGenerator Perl module - and you get to utilize all the other great modules written for the language.

The module I'm using for shuffling is not great at all in terms of popularity, but it is my own creation and I'm having a lot of fun replacing some tedious random number generation and array operations with it. The module takes some general laws of quantum physics - the phenomenon of a state of superposition, to be exact - and applies them to Perl variables. I'm not a physicist at all so don't expect it to be very accurate - the goal here is to allow for some very neat operations right in the code.

The normal usage of the module is creating a superposition of values - an object that tries to act as if it had all these values at once, like an array on steroids - and then collapsing it to get one of the states randomly. It makes choosing a random element out of a group of elements very easy, and is more declarative way of doing it, rather than imperative. Of course, it is one of the less exciting features of the module - I will talk about more exciting stuff a bit later.

The module is called Quantum::Superpositions::Lazy (that's a fairly long name, so we'll call it by its alias - Q::S::L) and is more or less a rewrite of a very old Quantum::Superpositions module by Damian Conway - a famous Perl programmer. I decided to develop a new module not only because the old one was no longer developed, but also because it was lacking some crucial features that I was interested in, like:

• It was not able assign to weights to states - all states had the same chance of occuring.
• It always kept all states and performed all the operations right away. Hence the ::Lazy part of my module, as it tries to perform operations as late as possible.
• It contained a lot of black magic, and was (in my opinion) a bit hard to handle due to that.

Setting up a playlist

A playlist will be just a filesystem directory with subdirectories categorizing the tracks, which are simply stored as mp3 files. Each category (or genre) will have a different chance of getting selected for the next song. To keep randomness in check, the same track from a category cannot be played before all tracks from the same category were played. This creates a rare situation where a track can be played twice in a row if it is selected as the last one and then the first one from a category - fixing it would require an additional condition, but the situation should be rare enough that we're not going to worry about it.

Since categories will be played based on a fixed chance - no matter how many songs are in them - the playlist must be hand crafted to meet one's needs. Assigning a high chance to a small category will cause the songs from it to have a very high chance of getting selected. Lets look at an example:

playlist
| - category_a
    | - song_1
    | - song_2
| - category_b
    | - song_3
    | - song_4
    | - song_5
    | - song_6

If we set weight of category_a to be 10 and the weight of category_b to 5, the chances of songs playing will be as follows:

weight sum: 15

category_a, songs: 2, weight: 10
    song chance: (10 / 15) / 2 * 100% = 33.(3)%
category_a, songs: 4, weight: 5
    song chance: (5 / 15) / 4 * 100% = 8.(3)%

Each individual song from category_a will be played four times as often as each individual song from category_b, but a careless programmer may have thought that they will only be twice as frequent. All in all, categories will be played exactly how was specified, but one will feel that they listen to only two songs most of the time.

Quantum-like shuffling

Now that we have a plan for a playlist, it is time to write code that will shuffle it. For this short presentation, we will only implement the get_next_file function, which will return the name of a file that got selected. If you want to see the code in full or without my interruptions, please refer to the file in my Github repository. Code between the repository and this article may differ a little, since I try to make it more readable here.

Lets start with pragmas, imports and common variables that are required:

use v5.24;
use warnings;
use Q::S::L qw(:all);
use Path::Tiny;

# current directory
my $current = path(__FILE__)->dirname;

# configuration
my $config = {
    genres => {
        category_a => 10,
        category_b => 5,
    }
};

The function will keep some state with the state Perl keyword, which causes a variable to only be initiazed on the first function call and to keep the state throughout the calls. We also define a superposition with my $shuffle and then call ->collapse on it to get a single state randomly. Before returning the result, we also push the randomed state to the $last array:

sub get_next_file
{
    state $last = []; # only initialized once

    my $shuffle = do { ... };

    my $choice = $shuffle->collapse;
    push @$last, $choice;

    return $choice;
}

Now to implement the ... part, we need to create a superposition that will read all the categories and tracks in each of them. We will use the category (genre) config defined above:

my @arr;
my $last_files = superpos($last->@*);
for my $genre (keys $config->{genres}->%*) {
    my @all_files = glob "$current/radio/$genre/*.mp3";

$last_files is a superposition that will be used to obtain a list of songs that have not yet been played this turn. @all_files should contain a list of all the mp3 files within the category. We can now create a narrowed list of files for the category:

my $pos = superpos(@all_files);
$pos = fetch_matches {
    every_state { $pos ne $last_files }
};

Okay, this one is much more complex, so lets spend a little while here.

In the inner block, we compare two superpositions with ne, which in Perl means not equal when comparing as strings:

$pos ne $last_files

This causes every state of $pos to be compared with ne against every state of $last_files. If $pos contains [track1, track2, track3] and $last_files contain [track1, track3], then the following comparisons will be performed:

track1 ne track1
track1 ne track3
track2 ne track1
track2 ne track3
track3 ne track1
track3 ne track3

Now, to obtain a result from these comparisons, we need to join them somehow. I call this a reduction strategy, and there are currently three of them - "any", "all" and "one". By default, "any" strategy is used, which would create the following operation:

track1 ne track1 ||
track1 ne track3 ||
track2 ne track1 ||
track2 ne track3 ||
track3 ne track1 ||
track3 ne track3

Can you see the problem here?

Using ne with "any" strategy is often a mistake. It will work if both superpositions have a single element, but if we have two in either of them, it will always be true that one is not equal to the other. track1 ne track3 is enough to cause the entire operation to return true, even though an eq operation (which is the opposite of ne) will also return true. I'm considering introducing an exception to the "any by default" rule in the module, but for now I have decided to keep it as it is.

Thankfully we can control the reduction strategy by wrapping the operation in a function call:

every_state { $pos ne $last_files }

Now "all" strategy will be used, which will produce the following operation, which is correct:

track1 ne track1 &&
track1 ne track3 &&
track2 ne track1 &&
track2 ne track3 &&
track3 ne track1 &&
track3 ne track3

Now, lets move on to the next wrapper, which is fetch_states. Normally, ne operation between two superpositions would return a boolean value. In this case we don't want a boolean value, but we'd rather like to know which states from the first superposition meet the ne condition.

This is exactly what fetch_states is doing. A return value of it is a new superposition filled with states that matched. For a state to be included, it requires to meet the condition like the above, but a bit different:

track1 will be included if:
    track1 ne track1 &&
    track1 ne track3

track2 will be included if:
    track2 ne track1 &&
    track2 ne track3

track3 will be included if:
    track3 ne track1 &&
    track3 ne track3

From this example, only track2 will be included, which is what was expected.

With that out of the way, lets come back to the creation of $shuffle superposition. At this stage, it should look like this:

my @arr;
my $last_files = superpos($last->@*);
for my $genre (keys $config->{genres}->%*) {
    my @all_files = glob "$current/radio/$genre/*.mp3";

    my $pos = superpos(@all_files);
    $pos = fetch_matches {
        every_state { $pos ne $last_files }
    };

The $pos superposition for the current genre is more or less ready to be added to @arr which holds the states of the entire superposition, but we must first take care of clearing $last of files if all tracks were already played. This code will take care of that:

    if (!$pos->states->@*) {
        $pos = superpos(@all_files);
        $last = [grep { every_state { $_ ne $pos } } $last->@*];
    }

The ->states method returns a complete list of states for the superposition. If this is empty, we create it anew from the files found and remove all the files in this category from the last played files.

The last step is to populate the @arr array, and create a new superposition out of it outside the loop:

    push @arr, [$config->{genres}{$genre}, $pos];
}
superpos(\@arr);

Populating @arr is done with an array reference, which contains two elements. The first one is the weight of the state, and the second one is value, in this case the superposition we just created. The module is smart enough to collapse positions recursively, so collapsing the parent superposition will also collapse the nested superpositions.

Conclusion

With relatively short code we have achieved, in my opinion, quite a complex shuffling mechanism which includes:

• pure randomness within categories
• categories selected according to their weight
• playback history and avoiding duplications until all tracks are played

Capabilities of the module does not end here. It contains a built in statistics module, which can provide information on most probable states, median state and even expected deviation (if the data is numeric). It can also mutate superpositions with mathematical operations, string operations and even a custom, user-specified function. I am also actively developing it, so it should get better with every release.

(this article is also available on my personal blog)