Haskell显式递归与`iterate`

Question

在使用iterateHaskell 编写函数时,我发现具有显式递归的等效版本似乎明显更快 - 尽管我认为在Haskell中应该不赞成显式递归.

类似地,我期望GHC能够适当地内联/优化列表组合器,以便得到的机器代码至少类似地执行显式递归.

这是一个(不同的)示例,它还显示了我观察到的减速情况.

steps m n并且它的变体steps'计算Collat​​z步数n达到1的m次数,在尝试后放弃.

steps使用steps'列表函数时使用显式递归.

import Data.List (elemIndex)
import Control.Exception (evaluate)
import Control.DeepSeq (rnf)

collatz :: Int -> Int
collatz n
  | even n    = n `quot` 2
  | otherwise = 3 * n + 1

steps :: Int -> Int -> Maybe Int
steps m = go 0
  where go k n
          | n == 1    = Just k
          | k == m    = Nothing
          | otherwise = go (k+1) (collatz n)

steps' :: Int -> Int -> Maybe Int
steps' m = elemIndex 1 . take m . iterate collatz

main :: IO ()
main = evaluate $ rnf $ map (steps 800) $ [1..10^7]

我通过评估所有值来测试这些值10^7,每个值都放弃了800步骤.在我的机器上(编译ghc -O2),显式递归花了不到4秒(3.899s)但列表组合器花了大约5倍(19.922s).

在这种情况下,为什么显式递归会更好,并且有没有一种方法可以在保持性能的同时不使用显式递归来编写它？

Answer 1

更新:我为此错误提交了Trac 15426.

如果复制定义中的问题就会消失elemIndex,并findIndex为您的模块:

import Control.Exception (evaluate)
import Control.DeepSeq (rnf)

import Data.Maybe (listToMaybe)
import Data.List (findIndices)

elemIndex       :: Eq a => a -> [a] -> Maybe Int
elemIndex x     = findIndex (x==)

findIndex       :: (a -> Bool) -> [a] -> Maybe Int
findIndex p     = listToMaybe . findIndices p

collatz :: Int -> Int
collatz n
  | even n    = n `quot` 2
  | otherwise = 3 * n + 1

steps' :: Int -> Int -> Maybe Int
steps' m = elemIndex 1 . take m . iterate collatz

main :: IO ()
main = evaluate $ rnf $ map (steps' 800) $ [1..10^7]

问题似乎是GHC必须能够使这些融合得当.不幸的是,它们都没有被标记为无可比拟的Data.OldList.

允许findIndex参与融合的变化是相对较新的(参见Trac 14387),其中listToMaybe重新实现为foldr.所以,它可能还没有看到很多测试.