Haskell explicit recursion vs `iterate`

Question

While writing a function using iterate in Haskell, I found that an equivalent version with explicit recursion seemed noticeably faster - even though I believed that explicit recursion ought to be frowned upon in Haskell.

Similarly, I expected GHC to be able to inline/optimise list combinators appropriately so that the resulting machine code is at least similarly performing to the explicit recursion.

Here's a (different) example, which also displays the slowdown I observed.

steps m n and its variant steps' compute the number of Collatz steps n takes to reach 1, giving up after m attempts.

steps uses explicit recursion while steps' uses list functions.

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]

I tested these by evaluating for all values up to 10^7, each giving up after 800 steps. On my machine (compiled with ghc -O2), explicit recursion took just under 4 seconds (3.899s) but list combinators took about 5 times longer (19.922s).

Why is explicit recursion so much better in this case, and is there a way of writing this without explicit recursion while preserving performance?

Answer 1

Updated: I submitted Trac 15426 for this bug.

The problem disappears if you copy the definitions of elemIndex and findIndex into your module:

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]

The problem seems to be that these must be inlinable for GHC to get the fusion right. Unfortunately, neither of them is marked inlinable in Data.OldList.

The change to allow findIndex to participate in fusion is relatively recent (see Trac 14387) where listToMaybe was reimplemented as a foldr. So, it probably hasn't seen a lot of testing yet.