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