# Haskell explicit recursion vs `iterate`

• A+
Category：Languages

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.