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.

This entry was posted on December 29, 2010 at 8:14 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

16 Responses to “Perl 6 Fibonacci versus Haskell”

Dan Burton Says:
December 29, 2010 at 9:04 pm | Reply
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)
```
stingz Says:
December 29, 2010 at 9:51 pm | Reply
What is the performance difference? I like to hate on Haskell because it is still so inefficient.
- colomon Says:
  December 29, 2010 at 10:03 pm | Reply
  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:
    December 29, 2010 at 10:13 pm
    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:
  December 29, 2010 at 10:16 pm | Reply
  > ” 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:
    December 30, 2010 at 5:36 am
    *Audrey Tang.
  - stingz Says:
    December 30, 2010 at 1:51 pm
    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:
    December 30, 2010 at 10:37 pm
    Paul did you check the haskell programs? They are pretty hairy to say the least.
Dan Burton Says:
December 29, 2010 at 10:33 pm | Reply
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:
  December 29, 2010 at 10:44 pm | Reply
  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:
  December 29, 2010 at 11:31 pm | Reply
  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:
    December 30, 2010 at 12:13 am
    > But I’ll bet there’s a easy way to convince Haskell to do this too…
    
    In Haskell, it would just be (+).
- Brad Gilbert Says:
  January 1, 2015 at 12:58 am | Reply
  Finding out the 100,000th value takes less than 5 seconds on the latest Rakudo on MoarVM build. 2014-12-31. ( I actually ran it without the </dev/null, and the longest time was just over 4.5 sec )
```
    $ time perl6 -e'my @fib := 0, 1, 1, *+* ... *; say @fib[100_000]' </dev/null
    real	0m4.292s
    user	0m3.969s
    sys	0m0.285s
```
  ( The added 0 is for padding so I don’t have to subtract one from the index )
  - colomon Says:
    January 29, 2015 at 8:28 pm
    If you start with 0 you can leave out the second 1. 😉
Dean Says:
December 30, 2010 at 5:16 am | Reply
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.
Sanity Says:
September 23, 2011 at 2:18 pm | Reply
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.