Haskell 显式递归与“迭代”

Question

在 Haskell 中使用 iterate 编写函数时，我发现具有显式递归的等效版本似乎明显更快 - 尽管我认为显式递归在 Haskell。

同样，我希望 GHC 能够 inline/optimise 适当地列出组合器，以便生成的机器代码至少与显式递归执行类似。

这是一个（不同的）示例，它也显示了我观察到的减速。

steps m n 及其变体 steps' 计算 n 达到 1 所需的 Collatz 步数，在 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。所以，它可能还没有经过大量测试。

Haskell 显式递归与“迭代”

Haskell explicit recursion vs `iterate`

performance

haskell

loops

ghc

compiler-optimization