CODEWITHSUNDEEP
haskell
Adrian Z.
Adrian Z.

Reputation: 934

Performance of iterator list comprehension

I'm new to functional programming with Haskell and was wondering if there was any difference with performance between iterate and list comprehension. Right now I'm using last (takeWhile (< n) (iterate (2*) 1)) to get the highest power of two that can fit in a given number n. I would like to optimise this as much as possible. Is there a better way? Without the last it would return a list of powers of two lower than n. With the last it just returns the largest one.

Example: If I input 117 for n the output will be 64 and the list would be [1, 2, 4, 8, 16, 32, 64].

Upvotes: 0

Views: 332

Answers (3)

Roman Czyborra
Roman Czyborra

Reputation: 127

  largestPowerOfTwoIn n = until ((>n).(*2)) (*2) 1

where the Prelude.until idiom yields a constant-space tail-recursive iteration to your end result.

Upvotes: 0

OllieB
OllieB

Reputation: 1431

If it optimisation you're after, you're going about it the wrong way. It is generally always better to optimise the algorithm. (Warning, untested)

The basic algorithm for this is 2^(floor(log2(n)))

Why not:

myFunc :: Int -> [Int]
myFunc n = map (2^) list
    where list = [1..x]
          x = floor $ logBase 2 (fromIntegral n)

or if you just want the highest power of 2 to a number

myFunc2 :: Int -> Int
myFunc2 n = 2 ^ (floor $ logBase 2 (fromIntegral n))

Upvotes: 1

chepner
chepner

Reputation: 531345

A much simpler answer is to use recursion directly.

foo 1 = 1
foo x = 2 * foo (div x 2)

Upvotes: 0

Related Questions