- A+

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?

*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.