Shuffling my playlist with Perl and quantum mechanics
Tags: programming, perl, music
Published: 2021-02-05 09:40:24

# 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](https://metacpan.org/pod/Audio%3A%3AStreamGenerator) 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](https://metacpan.org/pod/Quantum%3A%3ASuperpositions%3A%3ALazy) (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](https://metacpan.org/pod/Quantum%3A%3ASuperpositions) 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](https://github.com/brtastic/perl-radio/blob/master/radio.pl). 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:

```perl
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:

```perl
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:

```perl
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:

```perl
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:

```perl
$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:

```perl
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:

```perl
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:

```perl
    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:

```perl
    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](https://bbrtj.eu/blog/article/shuffling-playlist))