Started learning Haskell today. So far, it's neat and only minimally annoying (stupid types). Knowing Perl and Elisp make it not too brain-stretchy. Actually compiling code feels odd...it's been probably since my last C++ class in 1999 that I compiled something written by myself.
One of the early examples in the tutorial I'm working through (YAHT) involves -- surprise -- the Fibonacci series, implemented recursively. Out of curiosity I wrote an iterative version in Perl and started running them side-by-side. First the code:
--
-- This is Haskell...
--
module Main
where
import IO
main = do
hSetBuffering stdin LineBuffering
putStrLn "Find which Fibonacci number?"
num <- getLine
putStrLn ("F[" ++ num ++ "] is " ++ show(fibo(read num)))
fibo 1 = 1
fibo 2 = 1
fibo n = fibo (n - 2) + fibo (n - 1)
#
# ...and this is Perl
#
$num = <>;
chomp $num;
$t1 = 1;
$t2 = 1;
for (1..$num) {
if ($_ == 1 || $_ == 2) {
$f = 1;
} else {
$f = $t1 + $t2;
$t1 = $t2;
$t2 = $f;
}
}
print "F[$num] is $f\n";
The Haskell code was compiled with no special options using ghc. The perl was run under Perl, twice the first time, so that perl(1) would be buffered. Things didn't get interesting until around the 30th number in the series:
mdxi@fornax:~$ time ./haskell/fibo_hs Find which Fibonacci number? 30 F[30] is 832040 real 0m0.672s user 0m0.432s sys 0m0.004s mdxi@fornax:~$ time perl fibo.pl 30 F[30] is 832040 real 0m0.240s user 0m0.002s sys 0m0.002s
This is where you can finally start to see a difference between recursive and iterative implementations. By 40 the difference was staggering:
mdxi@fornax:~$ time ./haskell/fibo_hs Find which Fibonacci number? 40 F[40] is 102334155 real 0m52.804s user 0m52.541s sys 0m0.024s mdxi@fornax:~$ time perl fibo.pl 40 F[40] is 102334155 real 0m0.256s user 0m0.002s sys 0m0.003s
It took the recursive implementation 1m26s (162% longer) to find number 41 and 2m17s (147% longer than 41; 240% longer than 40) to find number 42.
Meanwhile the iterative implementation took 0.43 seconds to find the 100th number and the same amount of time to find the 500th. At this point I figured my typing lag was taking most of the time, so I rewrote the perl to use command-line arguments (I don't know how to handle that in Haskell). With this change, the iterative approach took 0.005s to find the 1000th number of the sequence, and (0.014, 0.111)s to tell me that perl(1) considers the (10,000; 100,000)th numbers equivalent to infinity.
What does this tell us? Other than that I am easilly amused, pretty much just that: the flip side to TMTOWTDI is that not every way is the right way for the job at hand. But we all knew that already, right?
map head (iterate(\y->[x| x<-y, (x `mod` head(y) /= 0)]) [2..]) primen :: Int -> Int
primen n = (map head (iterate(\y->[x| x<-y, (x `mod` head(y) /= 0)]) [2..]))!!n