为什么Haskell列表理解比循环更快

Question

我是Haskell noob.在尝试循环和列表推导时,我发现列表理解比循环更快.Lisp理解使用取幂并且仍然更快.为什么？

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] ])))

Answer 1

首先是一些风格建议:

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

关于你的问题:lg不是真正的循环.它是一个尾递归函数,但仅此一点在Haskell中并没有多少说明.阻碍的主要因素是懒惰:如果累加器只是在thunk维度而不是它们的值中累积,那么懒惰只会产生大量的开销而没有任何可用性增益.

一种防止这种情况的简单方法是严格评估参数

{-# LANGUAGE BangPatterns     #-}

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

然而,由于这些问题,但也因为简洁/模块化/ ...,最好不要编写尾递归函数,而是使用更高级别的工具 - 列表推导本身往往不是那么好的性能,但是如果你用通用折叠等表达你的算法,你可以利用更多高性能的数据结构,例如未装箱的向量,而你的代码几乎没有变化.