Tag Archives: sort

A working bogosort in Perl6

It's not even mine actually. @moritz helped me with that. I couldn't remember the syntax for the reduce operator (and it's [<op>]), so here it is, in its full wikipedia glory.

@list .= pick(*) until [<=] @list

Here's a somewhat more complete example, that you can actually run:

my @list = 1, 2, 7, 4, 3;
@list .= pick(*) until [<=] @list;
say @list.perl;

This will bogosort the array (wikipedia), that is, shuffle it until it's ordered. Look at the Java version for a nice comparison.

Here's the explanation:

my @list = 1, 2, 7, 4, 3;

Declares the list. You don't need parens around the elements. If that was a deck of cards, you could write it as:

my @list = <A 2 3 4 5 6 7 8 9 J Q K>

The angular brackets <> are the equivalent of qw() in Perl 5. Following line is quite dense:

@list .= pick(*) until [<=] @list;

This can be written also as:

while not [<=] @list {
  @list .= pick(*)
}

As you can see, you don't need parens around the while condition. The [<=] @list bit is IINM a reduce operator for a list. For example, to sum all elements of a list, you'd use:

my @num = 1, 2, 3, 4;
say [+] @num;

So the [<=] operator applied to a list compares each element with the next one, then the result with the next one. Assuming @list = 2, 4, 8, 5, that is how I think it runs:

2 <= 4 (true, go on, last evaluated value is 4)
4 <= 8 (true, go on, last value is 8)
8 <= 5 (false, stop here, return value is false)

So, if the array is ordered, the while/until block is skipped. If the array is not ordered, execute the following:

@list .= pick(*)

.= is an operator for in-place method call. Writing that is equivalent to:

@list = @list.pick(*)

That in Perl 5 would be written as:

$list = SomeListObject->new(1, 2, 3, 4, 5);
$list->pick(???);

Actually, there wouldn't be any Perl 5 direct equivalent code, since the magic bit here (the *, aka "whatever") it's not even there. "whatever" is magic for "anything that's applicable here, until there's an end to it", or at least this is my ignorant interpretation of it… :)

So in this context, pick() is a method that returns a random element from a list. Together with *, it means pick a random element from any of the original @list. Mmmh. But then it should be equivalent to:

@list .= pick(@list)

But it's not, so pick(*) knows the right thing to do…
And it's clear that I don't know how pick() works :)
Anyway…

BTW, this is runnable code. If you want to try it, clone the rakudo repository, and run perl Configure.pl --gen-parrot to build it. Have fun!