However, if you check out the current repository, you'll find an example/quicksort.p6 that indeed works, using "multi sub" dispatch. I'll list you in the AUTHORS file, if you'd let me know your name.

The code in the repository looks like this:

use v6;

multi sub quicksort ( ) { () }

multi sub quicksort ( *$x, *@xs ) {
    my @pre  = @xs.grep{ $_ < $x };
    my @post = @xs.grep{ $_ >= $x };
    (@pre.quicksort, $x, @post.quicksort);
}

(1, 5, 2, 4, 3).quicksort.say;
[download]

I need to check with p6l folks on whether quicksort() can match a slurpy list this way. It is possible that quicksort( *[] ) would be a more accurate. Once I found out the answer, I'll fix the examples accordingly.

Thanks,
/Autrijus/

I'm very happy that you are checking out my code! There were multiple reasons that broke the quicksort example, chief among them being that "map" and "grep" had not been implemented. :-)

A little too much enthusiasm on my part there, perhaps. I saw something that looked like it could work, and did not actually check out if the internals were implemented :)

Thank you very much for this initiative autrijus. In my humble opinion, you deserve all the praise the Perl community can muster. Keep up the good work!

I'm having some trouble building Pugs right now, though. I am therefore unable to run your examples ... It looks like an issue with the generated Makefile. Building the darcs repository now fails with dmake complaining about:

dmake.exe: Error -- 'C:\dev\fun\pugs\pugs.exe' not found, and can't be made.

I tried to copy in the old executable from a previous install, but then it would not rebuild, even after resaving the files to rewrite their dates. Fetching the repository again didn't work either. I dont't have more time to investigate this now (I'm at work), but I'll see if can figure something out when I get home.

pernod
--
Mischief. Mayhem. Soap.

I think it's a dmake issue. Try tweaking the Makefile and replace all c:\dev\fun\pugs\pugs.exe to pugs.exe and let me know if it works?

Of course you can always do a cd src then ghc --make Main.hs by hand...

But if you do want multimethod dispatch, why immediately starting with a corner case? I am not sure that empty argument lists are supported (or even considered) in multi subs, as these are distinguished based on their signatures (long names). What is the signature of an empty argument list then?

But if you do want multimethod dispatch, why immediately starting with a corner case?

This may be a corner case for multi-method dispatch. But this kind of argument pattern matching (and by pattern matching I dont mean reg-exp) is quite common in functional languages, especially in recursive functions. Consider this these list functions in Standard ML, they all have an empty list case;

fun prod [ ] = 1
  | prod (h::t) = h * (prod t);

fun sum [ ] = 0
  | sum (h::t) = h + (sum t);

fun length [ ] = 0
  | length (h::t) = 1 + (length t);
[download]

When pattern matching against arguments in recursive functions like this (and in rescursive multi-method dispatch) it is always good to consider (and explicity code for) your edge cases, otherwise you run the risk of infinite recursion.
-stvn

Exactly, and to provide another example, this time in Haskell. The quicksort that serves as a model for the code in my original node:

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]
[download]

I really like the short and concise way this expresses the quicksort algorithm in almost mathematical notation. Although math was never my strong point, this way of talking about sets and their behaviour is in my opinion very powerful. Take a look at this node for some examples that are a bit closer to home.

pernod
--
Mischief. Mayhem. Soap.

But if you do want multimethod dispatch, why immediately starting with a corner case?

Because that quicksort implementation is cool :) I must admit that I haven't read all the apocalypses (I try from time to time, though), so I don't know much about the inner workings of what I'm attempting. I was just curious to see whether that neat Haskell snippet worked in Perl too.

pernod
--
Mischief. Mayhem. Soap.

Your post made me pretty much enthusiastic about Pugs, so I also gave it a try. Nice to see some Perl6 in work...

Although, neither I had luck with multiple dispatch. It seems to be broken in the current svn tree. What makes me think this is that I tried some of the sample codes at the FeatherweightPerl6 website to make work, but to no avail. I tend to get similar errors like you...

rg0now

Give Yet Another Haskell Tutorial a whirl, it's nice.

The only remaining hurdle is now that I do not seem to understand, what it actually does...:-) Can someone explain me very briefly how the code in the reply of autrijus (It now works. :)) operates?

Can someone explain me very briefly how the code in the reply of autrijus (It now works. :)) operates?

I'll give it a shot :)

1: multi sub quicksort ( ) { () }
2: multi sub quicksort ( *$x, *@xs ) {
3:     my @pre  = @xs.grep{ $_ < $x };
4:     my @post = @xs.grep{ $_ >= $x };
5:     (@pre.quicksort, $x, @post.quicksort);
6: }
7: (1, 5, 2, 4, 3).quicksort.say;
[download]

I'll assume you're familiar with the quicksort algorithm already, and the way it uses pivots. The first line states how we sort an empty list. Which is simply to return the empty list. This serves as the case for breaking recursion and avoiding infinite looping.

Line two defines a head and a tail, where the head $x is the first element in the list ('1' in the case of the call at line 7), while the tail @xs contains the remaining elements. Line 3 declares a list which contains all the elements from the tail that have a value smaller than $x.

@pre = @xs.grep{ $_ < $x } applies the built-in function grep to the tail. grep returns only the elements in @xs that are smaller than $x and puts them into @pre. This list is still unordered, but we now know that all the values in @pre are smaller than the pivot $x. Similarily for @post, but here we have all the bigger elements.

The magic kicks in at line 5, where we assemble the parts into a new list with the pivot in the middle. Remember though, that @pre and @post are as yet unsorted, so we apply quicksort to them recursively before we return the concatenated list.

Line 7 applies quicksort to a list, and then prints it to screen with the say. Say, I presume, is something similar to Haskell's show and Java's toString().

Clear as ink :D

pernod
--
Mischief. Mayhem. Soap.

Perhaps also helpful is the close equivalent in Perl5. No magical multi-methods, and a bit more verbose... but not too shabby. Come to think of it this should work fine in Perl6 as well, eh?

sub quicksort {
    return unless @_;
    my ($x, @xs) = @_;
    my @pre  = grep{ $_ < $x } @xs;
    my @post = grep{ $_ >= $x } @xs;
    (quicksort(@pre), $x, quicksort(@post));
}

my @a = quicksort(1, 5, 2, 4, 3);
print "@a\n";
[download]