Nested Signatures in Multi-dispatch

An earlier chapter showed how to use nested signatures to look deeper into data structures and extract parts of them. In the context of multiple dispatch, nested signatures take on a second task: they act as constraints to distinguish between the candidates. This means that it is possible to dispatch based upon the shape of a data structure. This brings Perl 6 a lot of the expressive power provided by pattern matching in various functional languages.

Some algorithms have very tidy and natural expressions with this feature, especially those which recurse to a simple base case. Consider quicksort. The base case is that of the empty list, which trivially sorts to the empty list. A Perl 6 version might be:

    multi quicksort([]) { () }

The [] declares an empty nested signature for the first positional parameter. Additionally, it requires that the first positional parameter be an indexable item--anything that would match the @ sigil. The signature will only match if the multi has a single parameter which is an empty list.

The other case is a list which contains at least one value--the pivot--and possibly other values to partition according to the pivot. The rest of quicksort is a couple of recursive calls to sort both partitions:

    multi quicksort([$pivot, *@rest]) {
        my @before = @rest.grep({ $_ <= $pivot });
        my @after  = @rest.grep({ $_ >  $pivot });

        return quicksort(@before), $pivot, quicksort(@after);
    }