💡 101. Quick sort in Perl 6

Today, let’s look at another, and presumably the most well known method of sorting data, Quick sort.

The algorithm requires you to select the so-called pivot, one of the element from the data, and split the rest in two parts: the elements less than the pivot, and the elements more or equals to the pivot. Each part is then recursively sorted again. On each iteration, the parts become smaller and smaller until the sublists are trivial data sets of one or even zero elements.

A separate theory is how to choose the right pivot. There are a few methods, for example, taking a value from the middle of the list, or taking the first item, or the last, or a random item. There are also more complicated methods, and you can tune it to achieve the best performance on your type of data sets.

For simplicity, let’s choose the first element as a pivot, and here is the code:

sub quick-sort(@data) {    
    return @data if @data.elems <= 1;

    my $pivot = @data[0];

    my @left;
    my @right;

    for @data[1..*] -> $x {
        if $x < $pivot {
            push @left, $x;
        }
        else {
            push @right, $x;
        }
    }

    return flat(quick-sort(@left), $pivot, quick-sort(@right));
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
@data = quick-sort @data;
say @data;

Unlike the previous examples of Bubble sort, this program does not sort in-place but returns a new list instead.

Now it is time to transform the code to make it more Perl 6-ish.

Multi-subs come for the rescue again, which while increasing the number of lines of code, make the whole algorithm easier to catch at a first glance.

multi sub quick-sort(@data where @data.elems <= 1) {
    return @data;
}

multi sub quick-sort(@data where @data.elems > 1) {
    my $pivot = @data[0];

    . . .
}

Now, take a look at these two pieces:

my $pivot = @data[0];

. . .

for @data[1..*] -> $x {

The first element needs to be taken, and the rest of the algorithm only deals with the rest of the list. Currently, this is achieved by taking an element and a slice, but there’s a shift method that does exactly what we need, and removes the element from the data. So, let’s use it:

my $pivot = @data.shift;

. . .

for @data -> $x {

The next comes the ifelse selection, which can be effectively (although maybe a bit less efficiently) be replaced with the two greps: one selecting the part prior to the pivot, another selecting the rest.

my @left = @data.grep(* < $pivot);
my @right = @data.grep(* >= $pivot);

Basically, that’s it. What you can also do is to get rid of temporary variables and put the filters to the return statement:

return flat(
    quick-sort(@data.grep(* < $pivot)),
    $pivot,
    quick-sort(@data.grep(* >= $pivot))
);

It all worked before this last change, but now it is broken:

$ perl6 quick-sort.pl 
Cannot call 'pop' on an immutable 'List'
   in sub quick-sort at 3.pl line 6
   in sub quick-sort at 3.pl line 8
   in block <unit> at 3.pl line 12

The problem is that you need to return a single list of numbers, but each subcall of quick-sort returns its own lists.

You can easily address the issue by slurping the elements by putting a * before the function argument:

multi sub quick-sort(*@data where @data.elems > 1) {
    . . .

The final code looks like this:

multi sub quick-sort(*@data where @data.elems <= 1) {
    return @data;
}

multi sub quick-sort(*@data where @data.elems > 1) {
    my $pivot = @data.shift;

    return flat(
        quick-sort(@data.grep(* < $pivot)),
        $pivot,
        quick-sort(@data.grep(* >= $pivot))
    );
}

Instead of using the flat routine, you can also flat each list independently using the |:

return
    |quick-sort(@data.grep(* < $pivot)),
    $pivot,
    |quick-sort(@data.grep(* >= $pivot));

But I think it is still better to have a couple of understandable intermediate variables to avoid punctuation noise:

multi sub quick-sort(@data where @data.elems <= 1) {
    return @data;
}

multi sub quick-sort(@data where @data.elems > 1) {
    my $pivot = @data.shift;

    my @left = @data.grep(* < $pivot);
    my @right = @data.grep(* >= $pivot);

    return flat(quick-sort(@left), $pivot, quick-sort(@right));
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
@data = quick-sort @data;
say @data;

As a home work, create an implementation of the Quick sort algorithm that sorts the data in-place.

The code is available on GitHub, you are welcome to join this journey too!

And let me update the post with based on some comments on Reddit.

First, instead of two greps, it was nice to use some function that does the separation in one go (as it was in the original program with if and else). Actually, Perl 6 has one. It is called classify, and it returns a hash, where the keys are all the possible values of the condition. In our case, it will be True (when the element is less than the pivot), and False otherwise.

multi sub quick-sort(@data where @data.elems > 1) {
    my $pivot = @data.shift;

    my %part = @data.classify(* < $pivot);

    return flat(
        quick-sort(%part{True} // []), 
        $pivot,
        quick-sort(%part{False} // [])
    );
}

As it may happen that all elements are on the same side of the pivot, you need to make sure you pass an empty list in that case (thus, // []).

The second change will lead to the the code similar to what is published (as of today) on Rosettacode. Indeed, if our choice of the pivot is the first element, than it is possible to separate it in the function signature instead of manually taking the item in the code. You can also simplify the signature of the first multi-method:

multi sub quick-sort([]) {
    return [];
}

multi sub quick-sort([$pivot, *@data]) {
    my %part = @data.classify(* < $pivot);

    return flat(
        quick-sort(%part{True} // []),
        $pivot,
        quick-sort(%part{False} // [])
    );
}

Rosettacode’s code also does not have a return statement. You can do that too, while I prefer having an explicit return in the function.

Can you suggest any further clever change?

💡 100. Bubble sort in Perl 6

Hey everyone, let’s implement some algorithms in Perl 6.

The first one will be the classical Bubble sort. In essence, you scan the data from left to right and swap the two adjacent items if they are not ordered properly yet. Repeat until the whole data list is ordered.

Here’s the initial straightforward implementation:

sub bubble-sort(@data) {
    my Bool $done = False;
    while !$done {
        $done = True;
        for 1 .. @data.elems - 1 -> $n {
            if @data[$n - 1] > @data[$n] {
                (@data[$n - 1], @data[$n]) = 
                    (@data[$n], @data[$n - 1]);
                $done = False;
            }
        }
    }
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
bubble-sort @data;
say @data;

This implementation does in-place sorting, but you don’t need to declare the function argument as is rw. Actually, the compiler will tell you that that is redundant and will stop further compilation:

For parameter '@data', '@' sigil containers don't need 'is rw' to be writable
Can only use 'is rw' on a scalar ('$' sigil) parameter, not '@data'

Another place which I’d like to take a more precise look at is swapping the two array elements:

(@data[$n - 1], @data[$n]) = (@data[$n], @data[$n - 1]);

Now, as the program is ready and we can confirm it works correctly, let’s transform it to make it more expressive (although maybe a bit less efficient).

$ perl6 bubble-sort.pl6 
[1 1 2 2 4 5 7 9 10 46 78]

The first step would be to simplify the swapping code. On both sides of the equals sign, we are working with the same two elements, with indices $n and $n - 1. It is possible to call the reverse method on the list of two elements and assign it back to it:

(@data[$n - 1], @data[$n]).=reverse;

This can be simplified further by using an array slice:

@data[$n - 1, $n].=reverse;

As you can see, the parentheses are not needed any more. The only question, which you have to answer yourself, is whether to surround the .= operator with spaces or not. On one hand, this is a method call (thus, no spaces), on another, it is an assignment (thus, spaces).

OK, what’s next? Of course, the if statement can be written as a postfix condition, but there are two lines of code in the if block. At this point, I can make a decision to trade between the beauty of code and the efficiency, and get rid of the Boolean $done flag.

sub bubble-sort(@data) {
    for 1 .. @data.elems - 1 -> $n {
        if @data[$n - 1] > @data[$n] {
            @data[$n - 1, $n].=reverse;
        }
    }
    bubble-sort(@data) unless [<=] @data;
}

This step also allowed to remove the while block. At the end of the function, a recursive call is done (again, maybe less efficient, but who cares), and the condition to check if the array is already sorted is now explicit:

unless [<=] @data

After all that, it is now possible to append a postfix if:

@data[$n - 1, $n].=reverse if @data[$n - 1] > @data[$n]

And even the postfix for:

@data[$_ - 1, $_].=reverse
    if @data[$_ - 1] > @data[$_]
        for 1 .. @data.elems - 1;

Also, why not make the condition using both the slice and the reduction operator as we’ve already done in other parts of the function:

@data[$_ - 1, $_].=reverse
    if [>] @data[$_ - 1, $_]
        for 1 .. @data.elems - 1;

The next step is to reduce the range 1 .. @data.elems - 1, which is OK but contains a bit too many elements, which can be removed. The -1 part can be replaced with an open range:

for 1 ..^ @data.elems;

After which the elems call is not needed, and Perl 6 can do that for us:

for 1 ..^ @data;

And here’s the current state of the code:

sub bubble-sort(@data) {
    @data[$_ - 1, $_] .= reverse
        if [>] @data[$_ - 1, $_]
            for 1 ..^ @data;
        
    bubble-sort(@data) unless [<=] @data;
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
bubble-sort @data;
say @data;

Before we stop for now, here’s another modification that is possible. In general, recursion in Perl 6 can be implemented via multi-subs. Instead of branching inside the function, let the compiler do the job based on data:

multi sub bubble-sort(@data where [<=] @data) {}

multi sub bubble-sort(@data where ![<=] @data) {
    @data[$_ - 1, $_] .= reverse
        if [>] @data[$_ - 1, $_]
            for 1 ..^ @data;
    bubble-sort(@data);
}

If you don’t like the [<=] check (as it should scan the whole list), here’s a brute-force version with another loop layer:

sub bubble-sort(@data) {
    for ^@data {
        @data[$_ - 1, $_] .= reverse
            if [>] @data[$_ - 1, $_] for 1 ..^ @data;
    }
}

The two for loops can be joined using the cross operator:

sub bubble-sort(@data) {
    for ^@data X 1 ..^ @data {
        my $n = $_[1];
        @data[$n - 1, $n] .= reverse if [>] @data[$n - 1, $n];
    }
}

You are invited to work on this code further. I am really curious if and how this can be done even shorter (for example, how to re-use the slice).

The source codes of the above-shown programs are available on GitHub.

📺 Creating a compiler in Perl 6

At the German Perl Workshop 2019 in Munich, I gave a presentation about how to create compilers and interpreters using Perl 6 grammars. This talk differs from my previous talks on this subject, so if you’ve seen them, I hope you will also enjoy this one. There was a video recording during the talk, I assume that the video will appear reasonably soon.

📺 Perl 6 as a new tool for language compilers

Here’s my recent talk from FOSDEM in Brussels, given on 3 February 2019.

Perl 6 grammars are a great way to describe the grammar and implement an interpreter or a compiler of DSL or a programming language. In this talk, I will demonstrate how you can do it. During the talk, we will create an interpreter for a tiny programming language.

The engine behind the implementation will be the so-called Grammars that are available in today’s Perl 6. We will create the full language specification and describe all the actions it needs to do to execute the program.

The great part is that you no longer need to split your language implementation in traditional phases: lexer, parser, etc. Neither you need a compiler of compilers to process the formal grammar rules and emit the lexer/parse code that you will later use in your compiler. All you need is just to write some Perl 6 code. You even don’t need to be a specialist in compilers or learn numerous tools like bizon etc. to create your own language in a few hours.

🎄 26/25. Overview of the Perl 6 One-Liner Advent Calendar 2018

The Perl 6 One-Liner Advent Calendar 2018 is over! Let’s make a quick overview of what we have covered so far. There were a few themes covered.

First, some one-liners from the Perl 6 Calendar 2019 were explained in more detail. We looked at how to generate random passwords and random integers, how to print current date, and at how good Perl 6 is doing with Unicode.

Second, a number of problems from Project Euler were solved in Perl 6: #1 grepping dividable numbers, #2 adding up even Fibonacci numbers, #4 testing palindromic numbers, #5 finding the least common divider, #7 printing the given Fibonacci number, #13 computing a sum of big numbers, #19 counting Sundays and counting them differently, #25 finding a Fibonacci number of the given length, and #34 finding a sum of the numbers that are equal to the sum of factorials of their digits.

Third, we looked at some isolated elements of Perl 6 syntax, such as meta-operator X, range and sequence operators, reduction operator, or how rational numbers work in Perl 6 and how to use complex number in geometry. A numerous times, we were using the built-in routines map and grep, and the WhateverCode objects.

Fourth, we explored a few common sequences: Fibonacci numbers and prime numbers, or the Leibnitz series for computing the value of π.

Fifth, we solved a few golf problems: how to print the first Fibonacci numbers, or how to print the first prime numbers. A separate post was dedicated to the ideas of how to make the code more compact.

Sixth, we moved on to command-line tools, covered the basic options that Rakudo supports and created a few one-liners for manipulating files, such as the one for renaming a bunch of files, or reversing a text file, or merging two files horizontally, or computing totals from the table columns, or how to read from multiple input files.

As a bonus, the posts from the One-Liner calendar have been translated to Chines, thanks to Chen Yf (if I decoded the name correctly).

Also, don’t forget about my article in the regular Perl 6 Advent Calendar about how to make the grammar more compact.

🎄 25/25. Tips and ideas for the Perl 6 Golf code

Welcome to Day 25, the last day of the Perl 6 One-Liner Advent Calendar! Traditional advent calendars have only 24 entries, and our bonus post today will be dedicated to some tips and tricks that you can use in Perl 6 golf contest.

There is a great site, code-golf.io, where you can try solving a number of problems, and move Perl 6 to the top scores. I suspect that many problems can benefit from the techniques that were covered in the previous days of this One-Liner Advent Calendar.

Omitting topic variable

If methods are called on the topic variable $_, then the name of the variable is not really needed for Perl 6 to understand what you are talking about, so, avoid explicitly naming the topic variable:

$_.say for 1..10

Using ranges for making loops

Ranges in Perl are great things to express loop details: in a few characters, you specify both the initial and final state of the loop variable. Postfix forms are usually shorter.

for 1..10 {.say}
.say for 1..10

Think if you can count from 0, in which case, a caret character can be used to get a range starting from 0. The following code prints the numbers 0 to 9:

.say for ^10

Choosing between a range and a sequence

In loops, sequences can work exactly the same as a range would do. The choice may depend on whether the Golf software counts bytes or Unicode characters. In the first case, the two dots of a range are preferable over the three dots of a range. In the second case, use a Unicode character:

.say for 1..10
.say for 1...10
.say for 1…10

When you need to count downwards, sequences are your friends, as they can deduce the direction of changing the loop counter:

.say for 10…1

Using map instead of a loop

In some cases, especially when you have to make more than one action with the loop variable, try using map to iterate over all the values:

(^10).map: *.say

Omitting parentheses

Unlike Perl 5, Perl 6 does not force you to use parentheses in condition checks in the regular form:

if ($x > 0) {say $x;exit}
if $x > 0 {say $x;exit}

Sometimes, you will want to omit parentheses in function calls, too.

Neither you need parentheses when declaring arrays or hashes. With arrays, use the quoting construct on top of that:

my @a = ('alpha', 'beta')
my @b=<alpha beta>

Using chained comparisons

Another interesting feature is using more than one condition in a single expression:

 say $z if $x < 10 < $y

Choosing between methods and functions

In many cases, you can choose between calling a function and using a method. Method calls can be additionally chained after each other, so you can save a lot of parentheses or spaces:

(^10).map({.sin}).grep: *>0 

When there exist both a method and a stand-alone function, method call is often shorter or at least the same length if you omit parentheses.

abs($x)
abs $x
$x.abs

Using Unicode characters

Perl 6 operators often have Unicode equivalents, where you can express a wordy construct with a single character. Compare:

if $x=~=$y
if $x≅$y

Built-in constants are also available in the Unicode space, for example, pi vs π, or Inf vs .

There are many numbers, both small and big, that can be replaced with a single Unicode symbol: 1/3 vs , or 20 vs , or 100 vs .

Using superscripts

Superscripts are great for calculating powers. Compare:

say $x**2
$x².say

Using \ to make sigilless variables

Don’t forget about the the following way of binding containers and creating a kind of a sigilless variable:

my \a=42;say a

Using default parameters

When you are working with functions or class methods, check if there are default values in their signatures. Also check if there is an alternative variant with positional arguments. Compare, for example, three ways of creating a date object.

Date.new(year=>2019,month=>1,day=>1)
Date.new(year=>2019)
Date.new(2019,1,1)

Using && instead of if

Boolean expressions can save a few characters, as Perl will not calculate the second condition if the first gives the result already. For example:

.say if $x>0   
$x>0&&.say

Choosing between put vs say

Finally, sometimes it is better to use put instead of say. In some cases, you will be free from parentheses in the output when printing arrays, for example. In some other cases you will get all values instead of concise output when working with ranges, for example:

> say 1..10
1..10
> put 1..10
1 2 3 4 5 6 7 8 9 10

Till next year!

You can also find many interesting ideas in the last year’s advent post by Aleks-Daniel Jakimenko-Aleksejev.

But this time, this Perl 6 One-Line Advent Calendar is completely over. There will be one more post with an overview of everything published in the last 25 days.

I wish you all the best with your further Perl 6 adventure, would it be one-liners or industrial-scale applications. See you next year in another advent calendar, but don’t forget that perl6.online continues its work, and more posts will be published during the next 2019 year!