Why Haskell list comprehension is faster than loop

Question

I'm a Haskell noob. And while experimenting with loops and list comprehensions I have discovered that list comprehension is faster than a loop. Lisp comprehension uses exponentiation and is still faster. Why?

lg :: Int -> Int -> Int -> Int
lg s e a =
  if s < e
  then
  if even s
  then
    lg (s+1) e (a+1)
  else
    lg (s+1) e (a*2)
  else
    a

loopGrowth :: Int -> Int
loopGrowth x = lg 0 x 0

calcGrowth :: Int -> Int
calcGrowth y =
  last (take (y+1) (tail (join [ [2 ^ x - 2 ,2 ^ x - 1] | x <- [1..50] ])))

In general for performance-related questions (as said in the Haskell tag FAQ!), please make sure you've actually used meaningful test cases, and considered optimisation options. You should tell us exactly what you've tested, and what timings you got. Your two approaches are so different (they do not even give the same results!) that I find it hard to understand how you even tried to compare them. — leftaroundabout
– leftaroundabout, Commented Feb 11, 2015 at 11:08
@leftaroundabout There's an off-by-one error, but otherwise they give the same results. — Ørjan Johansen
– Ørjan Johansen, Commented Feb 11, 2015 at 16:53

leftaroundabout · Accepted Answer · 2015-02-11 11:13:44Z

5

First some style advice:

lg s e a
  | s >= e     = a
  | even s     = lg (s+1) e (a+1)
  | otherwise  = lg (s+1) e (a*2)

Regarding your question: lg is not really a loop. It's a tail-recursive function, but that alone doesn't say much in Haskell. The main thing that gets in the way is lazyness: if the accumulators are only accumulated in the thunk-dimension, rather than their values, lazyness merely builds up an enourmous amount of overhead without any usability gain.

A simple way to prevent this is to evaluate arguments strictly, with

{-# LANGUAGE BangPatterns     #-}

lg' s e !a
  | s >= e     = a
  | even s     = lg' (s+1) e (a+1)
  | otherwise  = lg' (s+1) e (a*2)

However, because of such issues but also because of conciseness/modularity/..., it is rather preferred not to write tail-recursive functions at all but use higher level-tools – list comprehensions themselves are often not that great performance-wise, but if you express your algorithms in terms of generic folds etc. you can utilise much more performant data structures such as unboxed vectors with little changes to your code.

edited Feb 11, 2015 at 11:13

answered Feb 11, 2015 at 11:05

leftaroundabout

121k6 gold badges185 silver badges337 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dfeuer Over a year ago

If you compile with -O2 and use the type signature indicated by the OP, GHC figures out the strictness on its own. I think Ørjan Johansen got this one.

Ørjan Johansen · Accepted Answer · 2015-02-11 23:37:20Z

4

Apart from the more complicated thunk issues @leftaroundabout mentions, I can think of two algorithmic reasons why the list comprehension could be more efficient than you think:

Because of laziness, only one of the list elements is actually evaluated. So only one exponentiation is performed.
Haskell's ^ is more clever than simply multiplying in a loop: It uses division by 2 internally to greatly reduce the number of multiplications needed. E.g. x^8 becomes "essentially" let x2 = x*x; x4 = x2*x2 in x4*x4. (EDIT: As @dfeuer points out, this is known as "fast exponentiation" or "exponentiation by squaring".)

edited Feb 11, 2015 at 23:37

answered Feb 11, 2015 at 17:00

Ørjan Johansen

18.2k3 gold badges45 silver badges53 bronze badges

2 Comments

dfeuer Over a year ago

You might want to mention that the algorithm is called "fast exponentiation", or "exponentiation by squaring".

leftaroundabout Over a year ago

+1, this does indeed much better adress the specific code the OP posted than my answer. — — — — — — — — — — — Oh, right, I still can't start comments with "+1", but wasn't it possible to disable this by adding enough text? Hm, I think I read that in this post on meta... oh my, it's such a useless restriction... (Sorry for the spam.)

Collectives™ on Stack Overflow

Why Haskell list comprehension is faster than loop

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related