Two simple codes to generate divisors of a number. Why is the recursive one faster?
factors, haskell, higher-order-functions, performance, recursion
Solution
The recursive version is not in general faster than the list-based version. This is because the GHC compiler employs List fusion optimizations when a computation follows a certain pattern. This means that list generators and "list transformers" might be fused into one big generator instead.
However, when you use `$!`, you basically tell the compiler to "Please produce the first cons of this list before performing the next step." This means that GHC is forced to at least compute one intermediate list element, which disables the whole fusion optimization entirely.
So, the second algorithm is slower, because you produce intermediate lists that have to be constructed and destructed, while the recursive algorithm simply produces a single list straight away.
Problem
While solving a problem, I had to calculate the divisors of a number. I have two implementations that produce all divisors > 1 for a given number. The first is using simple recursion: ``` divisors :: Int64 -> [Int64] divisors k = divisors' 2 k where divisors' n k | n*n > k = [k] | n*n == k = [n, k] | k `mod` n == 0 = (n:(k `div` n):result) | otherwise = result where result = divisors' (n+1) k ``` The second one uses list processing functions from the Prelude: ``` divisors2 :: Int64 -> [Int64] divisors2 k = k : (concatMap (\x -> [x, k `div` x]) $! filter (\x -> k `mod` x == 0) $! takeWhile (\x -> x*x <= k) [2..]) ``` I find that the first implementation is faster (I printed the whole list returned, so that no part of the result remains unevaluated due to laziness). The two implementations produce differently ordered divisors, but that is not a problem for me. (In fact, if k is a perfect square, the square root is output twice in the second implementation - again not a problem). In general are such recursive implementations faster in Haskell? Also, I would appreciate any pointers to make either of these codes faster. Thanks! EDIT: Here is the code I am using to compare these two implementations for performance: https://gist.github.com/3414372 Here are my timing measurements: Using divisor2 with strict evaluation ($!) ``` $ ghc --make -O2 div.hs [1 of 1] Compiling Main ( div.hs, div.o ) Linking div ... $ time ./div > /tmp/out1 real 0m7.651s user 0m7.604s sys 0m0.012s ``` Using divisors2 with lazy evaluation ($): ``` $ ghc --make -O2 div.hs [1 of 1] Compiling Main ( div.hs, div.o ) Linking div ... $ time ./div > /tmp/out1 real 0m7.461s user 0m7.444s sys 0m0.012s ``` Using function divisors ``` $ ghc --make -O2 div.hs [1 of 1] Compiling Main ( div.hs, div.o ) Linking div ... $ time ./div > /tmp/out1 real 0m7.058s user 0m7.036s sys 0m0.020s ```