haskell length runtime O(1) or O(n)

Question

I was working on a Haskell assignment and I was trying think of ways to make my code faster. For example, my factors function below finds the number of divisors of some integer.

factors :: Int -> Int
factors x = length [n | n <- [1..x], mod x n == 0]

However, it occurred to me that I could make my code faster by avoiding usage of "length".

factors :: Int -> Int
factors x = go 1
  where
    go :: Int -> Int
    go i
      | i == x        = 1
      | mod x i == 0  = 1 + go (i + 1)
      | otherwise     = go (i + 1)

I was wondering if Haskell's length function is O(n) like strlen() in C or O(1) like String.length() in Java.

Also, is there a better or more efficient of writing my code?

Answer 1

In my estimation, contrary to the accepted answer, you can in fact infer the complexity of length (and many other functions) just by looking at the definition of [a]:

Prelude> :info []
data [] a = [] | a : [a]    -- Defined in ‘GHC.Types’

Lists are inductively-defined; you can see from that definition (which is almost just regular haskell) that at the top level a list is either the constructor [] or :. Clearly length must recurse n times on this structure and so would have to be O(n).

It's very important to be able to reason at least intuitively in this way, in particular about lists which are ubiquitous. e.g. quick what's the complexity of (!!)?

If you want to do a deep dive into formally reasoning about time complexity in the presence of laziness then you'll need to pick up "Purely Functional Data Structures" by Okasaki.

Answer 2

Also, is there a better or more efficient of writing my code?

Integer factorization is one of the most famous problems. There surely have been proposed a lot of algorithms for that, even if I am not expert enough to make a recommendation (CS.SE is around the corner, and can help on that, if needed). None of such proposals is polynomial time, but this doesn't stop them to be faster than the trivial approach.

Even without looking at the literature, a few simple optimizations can be found.

• The original code scans the whole list [1..x], but this is not needed. We could stop at sqrt x, since after that there are no longer divisors.

• Even more: after we find a divisor m, we could divide x by m (as many times as possible), and recurse with this new number. E.g. if x = 1000 after we try m=2, we compute 1000 -> 500 -> 250 -> 125, and then find the new divisors (larger than 2) in 125. Note how this made the number much smaller.

I will leave implementing this strategies in Haskell as an exercise :-P