Haskell显式递归vs“`iterate`”

Question

在Haskell中使用iterate编写函数时，我发现具有显式递归的等效版本似乎要快得多--尽管我认为在Haskell中应该反对显式递归。

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

这里有一个(不同的)例子，它也显示了我观察到的减速。

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

更新:我为这个bug提交了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。所以，它可能还没有看到太多的测试。