Why is this Haskell expression so slow?

Question

I'm working on Project Euler Problem 14. Here's my solution.

import Data.List

collatzLength :: Int->Int
collatzLength 1 = 1
collatzLength n | odd n = 1 + collatzLength (3 * n + 1)
                | even n = 1 + collatzLength (n `quot` 2)

maxTuple :: (Int, Int)->(Int, Int)->Ordering
maxTuple (x1, x2) (y1, y2)  | x1 > y1 = GT
                | x1 < y1 = LT
                | otherwise = EQ

I'm running the following out of GHCi

maximumBy maxTuple [(collatzLength x, x) | x <- [1..1000000]]

I know that if Haskell evaluated strictly, the time on this would be something like O(n³). Since Haskell evaluates lazily though, it seems like this should be some constant multiple of n. This has been running for nearly an hour now. Seems very unreasonable. Does anyone have any idea why?

I don't see why Haskell's laziness should make any difference to the complexity of this algorithm. — sepp2k
Your function collatzLength is not tail-recursive. This slows down the function and causes unneeded allocation. And your maxTuple is the same as comparing fst. — fuz
@sepp I don't really know how List Comprehensions are implemented. If they're using Map, if Haskell evaluated strictly, it seems like it would have to pass through the list multiple times. — afkbowflexin
@Josh That could indeed be a reason. IIRC this was an issue in other programs too, although I can't recall where. — fuz
Yeah, I didn't really think too hard about the evaluation. I rewrote collatzLength to be tail recursive and it's still slow. Also, I didn't compile this. It didn't seem like I should have to. — afkbowflexin

hammar hammar · Accepted Answer · 2011-08-20T21:42:44

You're assuming that the collatzLength function will be memoized. Haskell does not do automatic memoization. You'll need to do that yourself. Here's an example using the data-memocombinators package.

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]

This runs in about 1 second when compiled with -O2.

Why is this Haskell expression so slow?

3 Answers