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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: