A blog about Modern Perl, bioinformatics and anything else that I feel like rambling about.

Tuesday, November 24, 2009

Baby Haskell and Good Old Perl

I finally drank the functional, immutable and pure koolaid and started reading some Haskell books. And to exercise a bit, I began to tackle some of the problems from project Euler.

Problem 10 states: "Find the sum of all primes less than 2,000,000".

After finding out that it's only necessary to check for divisors less than the square root of the number, I blatantly stole this version from the Haskell Wiki:


If this doesn't give you a nerdgasm, I don't know what will. It creates an infinite list of primes by filtering an infinite list of odd numbers with the isPrime function. This function, in turn, uses the primes list itself to look for potential divisors. So basically, the list is defined recursively.

The solution then boils down to getting all primes smaller than two million from the infinite list, summing them and outputting the result.

Anyway, this beautiful solution got me wondering how the perl version would look. Here is my first attempt:


Ugh. I mean, it's not that bad, it has some interesting things going on like having an infinite stream of primes, but after being embelished by the Haskell version, this seems uninspired at best.

But then I thought that being CPAN (and not syntax) Perl's strength, I should take a look there. After no more than 30 seconds of searching, I found Math::Primality. Look how the Perl 5 version looks now:


This put a smile on my face. Perl may not be the most beautiful language around, but it has a JFDI attitude that I have yet to find elsewhere.

16 comments:

  1. all The images are broken :-(

    ReplyDelete
  2. ah, nm, github's back. (Another reason why gists are annoying :-)

    ReplyDelete
  3. With J:

    +/x:p:i._1 p:2000000

    I win. What was the point anyway?

    (See http://www.reddit.com/r/programming/comments/a7rey/baby_haskell_and_good_old_perl/c0g8lri too.)

    ReplyDelete
  4. If I understand it right the Haskell version uses primes recursively in it's own definition (and thus speeding the scanning a bit). If you want to make it interesting - add that to the Perl version :)

    ReplyDelete
  5. @frew: the haskell version (compiled without any flags) runs in little over 2 secs, while both the Perl versions run in ~ 40 secs on my laptop. However, as zby++ noted, the comparison is not exactly fair since the priming algorithm in my Perl version doesn't use previously calculated primes to search for possible factors, it just scans the whole list (it doesn't even filter out odd numbers).

    ReplyDelete
  6. @lasts: That's cool, I've heard nice things about J.
    And it isn't a contest, so sorry, I don't have a price for you.

    The point of the blogpost (if there is a point) was to just show why, despite some warts that Perl might have, it's still current thanks to the community behind it (CPAN being a product of that).

    ReplyDelete
  7. primes = 2 : filter isPrime [3,5..]
    isPrime n = not . any (`isDiv` n) . takeWhile (\x -> x^2 <= n) $ primes

    isDiv a b = b ` | mod` a == 0

    context: http://r6.ca/blog/20081116T213644Z.html

    ReplyDelete
  8. Oops, typo, the last line is:

    isDiv a b = b `mod` a == 0

    ReplyDelete
  9. nubBy divides [2..]
    where divides x y = x `mod` y == 0

    ReplyDelete
  10. Your comment box is really broken on Firefox. On two different machines I can't paste or even use the arrow keys.

    ReplyDelete
  11. #!/usr/bin/env perl
    #
    # revised.pl
    #
    # if doing this with just core Perl, here is
    # a more elegant program and it's faster
    #
    # apologies for lack of decent indentation in
    # the final comment

    use Modern::Perl;
    use List::Util qw/sum first/;

    my $limit = shift @ARGV;

    my @primes;

    sub check_prime {
    my $n = shift;
    return if $n <= 1;
    for my $p ( @primes ) {
    last if $p**2 > $n;
    return if ! ( $n % $p );
    }
    push @primes, $n;
    }

    check_prime($_) for 2 .. $limit;

    say sum @primes;

    __END__

    $ time perl original.pl 2000000
    142913828922

    real 0m47.097s
    user 0m45.820s
    sys 0m0.190s

    $ time perl revised.pl 2000000
    142913828922

    real 0m11.704s
    user 0m11.600s
    sys 0m0.060s

    ReplyDelete
  12. @dagolden: I like your version a lot! It actually uses the same algorithm that the haskell version, and it's pretty clear and concise.

    So the Haskell version runs in 2.5 seconds, and yours in 10.5 (on my laptop). Not too bad for a dynamic language, eh?

    ReplyDelete
  13. It's a bit of a cheat, since first() and sum() are implemented in XS/C. Still dynamic, but avoids some extra overhead. And it's not quite the Haskell algorithm, since it's not a stream, which would add more overhead. But for the task, it suffices.

    ReplyDelete
  14. Hi Zeroth Order! I should note that I posted a follow-up to your post on my blog. I'll be happy to hear any comments.

    ReplyDelete