John M. Dlugosz has asked for the wisdom of the Perl Monks concerning the following question:

I'm inspired by today's featured article in Wikipedia: Euclid's method for finding GCD.

Here is the pseudocode expressed literally in Perl 6, using the modern (modulo) approach. Note that the subtraction approach might prove useful in the quest to make it shorter. 

sub gcd ($a is copy, $b is copy -> Int)
 {
 # start of golf course
    while $b != 0 {
       my $t = $b;
       $b = $a % $b;
       $a = $t
       }
 # end of golf course option 1
    return $a
 # end, option 2
 }

[download]
The rules are to assume the structure provided and just write code for the body, as marked between the comments. You can either put the result in $a or have it be the last value for implicit return.

The parameters are not typed, so you can use strange things (not just Ints) if you want during the process, and the result is automatically converted to Int because the return is typed.

I wonder what cool Perl 6 features can be brought to bear, or what tools from the Functional Programming arsinal can be wielded? Feel free to exhibit these for their own sake, even if not a short golf.

Replies are listed 'Best First'.
Re: Euclidean algorithm Golf in Perl 6
by moritz (Cardinal) on Jun 18, 2009 at 16:28 UTC
    Two simple things you can do (also in Perl 5):

    You can get rid of the temporary $t by using list assignment: 

        while $b != 0 {
        ($b, $a) = ($a % $b, $b);
    }

    [download]

    Or you can resort to recursion, ignoring your boundaries to the golf court: 

    sub gcd ($a, $b) {
    return $a if !$b;
    gcd($b, $a % $b);
}

say gcd(24, 42);

    [download]

    For none of these I can see something where Perl 6 really plays its strengths.

    So maybe something completely else? This might work, but since nobody implements infix:<...> yet, I couldn't test it: 

    sub gcd ($a, $b) {
    ($a, $b ... { $^x % $^y || () })[*-1]
}

    [download]

    For example for gcd(42, 24) it would produce the list 42, 24, 18, 6. During the next call to the block it the $^x % $^y returns 0, and the block the empty list, ending the creation of the list. The last element is the gcd.

[reply]
[d/l]
[select]
      The last one is very interesting. Wouldn't the original arguments need to be sorted first, though? I think it only works if $a >= $b. Looking back at the original, it is the same way. The wikipedia article requires this for the modulo version (as well as the recursive version), but not for the subtraction version.

      Your last one vividly illustrates how the algorithm generates successive refinements.

      I also suppose that the "Golf" module, which would create 1-char Unicode aliases for a bunch of things, should include a symbol to mean "recursive call". Besides being shorter than naming the function again, you may want to do it with unnamed blocks, and &?ROUTINE is also rather verbose. ↺ perhaps?

[reply]
[d/l]
Re: Euclidean algorithm Golf in Perl 6
by tilly (Archbishop) on Jun 18, 2009 at 17:42 UTC
    I have never played with Perl 6, but (Golf): Sieve of Eratosthenes has lots of ideas for how to express Euclid's algorithm concisely in Perl 5. Likely some of those ideas will translate.
[reply]

Back to Seekers of Perl Wisdom