迭代器列表理解的性能

Question

我是Haskell函数式编程的新手，想知道迭代和列表理解之间的性能是否有什么不同。现在我用last (takeWhile (< n) (iterate (2*) 1))来得到一个给定数n的二次方的最高值。我想尽可能地优化它。有更好的方法吗？如果没有last，它将返回比n低2的幂的列表。对于last，它只返回最大的一个。

示例：如果我为n输入117，则输出为64，列表为[1, 2, 4, 8, 16, 32, 64]。

Answer 1

如果你追求的是it优化，那你就大错特错了。通常优化算法总是更好的。(警告，未经测试(

这方面的基本算法是2^(floor(log2(n((

为什么不：

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

或者如果你只想要一个数字的2的最高幂

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

Answer 2

更简单的答案是直接使用递归。

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

Answer 3

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

其中Prelude.until习惯用法为最终结果生成一个常量空间尾部递归迭代。