Perl 6 Fibonacci versus Haskell

There’s been some discussion on reddit today about whether

my @fib := 1, 1, *+* ...^ * >= 100;

is unreadable gibberish or not, with the following Haskell suggested as an easier-to-understand version.

fib = 1 : 1 : zipWith (+) fib (tail fib)

(I've "corrected" both versions so they start the sequence with 1, 1.)

The first thing to observe here is that this are not the same at all! The Perl 6 version is the Fibonacci numbers less than 100, while the Haskell version lazily generates the entire infinite sequence. If we simplify the Perl 6 to also be the (lazy) infinite Fibonacci sequence, we get the noticeably simpler

my @fib := 1, 1, *+* ... *;

To my (admittedly used to Perl 6) eye, this sequence is about as clean and straightforward as it is possible to get. We have the first two elements of the sequence:

1, 1

We have the operation to apply repeatedly to get the further elements of the sequence:

*+*

And we are told the sequence will go on forever:

... *

The *+* construct may be unfamiliar to people who aren't Perl 6 programmers, but I hardly think it is more conceptually difficult than referring to two recursive copies of the sequence you are building, as the Haskell version does. Instead, it directly represents the simple understanding of how to get the next element in the Fibonacci sequence in source code.

Of course, this being Perl, there is more than one way to do it. Here's a direct translation of the Haskell version into idiomatic Perl 6:

my @fib := 1, 1, (@fib Z+ @fib[1..*]);

Well, allowing the use of operators and metaoperators, that is, as zipWith (+) becomes Z+ and tail fib becomes @fib[1..*]. To the best of my knowledge no current Perl 6 implementation actually supports this. I'd be surprised if any Perl 6 programmer would prefer this version, but it is out there.

If you're insistent on writing function calls instead of operators, you could also say it

my @fib := 1, 1, zipwith(&[+], @fib, tail(@fib));

presuming you write a tail function, but that's an easy one-liner.

About these ads

14 Responses to “Perl 6 Fibonacci versus Haskell”

  1. Dan Burton Says:

    Writing the helper function “generateWith”, I can make Haskell look like the first Perl way mentioned. The only catch is that generateWith builds the list from right to left, so you have to reverse it to get the list you wanted.

    My Haskell skills are only so-so; I’m sure more advanced Haskellers could do some nifty unfolding trick.

    ((x:y:xs) `generateWith` f) stopCondition
        | stopCondition z = (x:y:xs)
        | otherwise = ((z:x:y:xs) `generateWith` f $ stopCondition
      where z = x `f` y
    
    (*+*) = (`generateWith` (+))
    
    fibs = reverse $ [1,1] *+* (>= 100)
    
  2. stingz Says:

    What is the performance difference? I like to hate on Haskell because it is still so inefficient.

    • colomon Says:

      I can’t speak for Haskell’s performance, but

      my @fib := 1, 1, *+* ... *;
      

      is quite efficient in Rakudo. It also effectively memoizes the results -- once you've calculated @fib[N], the result of the calculation will stay available until @fib goes out of scope.

      • Paul Says:

        It will be also be “memoized” in Haskell. Try this in ghci:

        let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
        let fib n = fibs !! n
        fib 100000 — take a few seconds
        fib 100000 — this time instantaneous

    • Paul Says:

      > ” I like to hate on Haskell because it is still so inefficient.”

      Hu. Haskell is a *fast* language! http://shootout.alioth.debian.org/u64q/which-programming-languages-are-fastest.php

      “Haskell is faster than C++, more concise than Perl, more regular than Python, more flexible than Ruby, more typeful than C#, more robust than Java, and has absolutely nothing in common with PHP.”
      — Autrijus Tang (Pugs leader)

      • anonymous Says:

        *Audrey Tang.

      • stingz Says:

        Except your source doesn’t match your claim. Haskell requires at median twice as long to execute as the c++ benchmarks, at worst thirty five times! In order of median it goes C, C++, ATS, Ada, Java, Go, Haskell

      • Pedro Says:

        Paul did you check the haskell programs? They are pretty hairy to say the least.

  3. Dan Burton Says:

    OK, I couldn’t resist fiddling with unfoldr, so here’s a better version that doesn’t require reversing, and thus can produce infinite lists. Instead of (…), you can give it a predicate like (>=100) to make it stop there.

    ((x,y) `genWith` f) stopCondition = unfoldr f' (x,y)
        where f' (a,b) | stopCondition z = Nothing
                       | otherwise       = Just (a, (b,z))
                           where z = a `f` b
    
    (...) = (\_ -> False)
    
    (*+*) = (`genWith` (+))
    
    fibs = (1,1) *+* (...)
    
    main = print $ (0:fibs) !! 100000
    

    I would imagine that my Haskell implementation is slower than Perl, but that remains to be proven. On my machine, the Haskell I wrote here took about 10 seconds to correctly find the 100,000th number in the sequence. (Well, tbh, I only eyeball-verified ~10 significant digits.) The zipWith Haskell code listed at the top of this article took about 8 seconds to do the same thing.

    • Dan Burton Says:

      This actually has erroneous behavior with the stop condition. It forgets to add the two right before the end. =P

      Put “x:y:” in front of the call to unfoldr, and put “Just (z” instead of “Just (a” to fix it.

    • colomon Says:

      Nice!

      The one tricky thing here is that *+* is not a special operator in Perl 6, it's just shorthand for creating a lambda function which takes two arguments and adds them. So you could also say something like *+1 to create an anonymous function which takes one argument and adds one to it, or *+*+* to create one which takes three arguments and adds them.

      But I'll bet there's a easy way to convince Haskell to do this too...

      As for speed, your code would have to be really bad Haskell to make it worse than really good Perl 6 code running in Rakudo. Rakudo is slow.

      • Micah Says:

        > But I’ll bet there’s a easy way to convince Haskell to do this too…

        In Haskell, it would just be (+).

  4. Dean Says:

    I’m not much a fan of the (in my opinion) excessive starification:

    my @fib := 1, 1, *+* …^ * >= 100;

    I’d be more likely to use something like:

    my @fib := 1, 1, { $^a + $^b } …^ * >= 100;

    Which, I think, makes the relation stand out a bit more prominantly.

  5. Sanity Says:

    Ugh, that perl code is pretty unreadable vs the haskell. Haskell just looks like normal math we already know. Perl, as always, looks like cartoon characters swearing.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: