listToMaybe doesn't participate in foldr/build fusion
I noticed that Data.OldList.findIndex
seems to use more memory than necessary, and that changing the definition of listToMaybe
to be in terms of foldr
fixed the situation.
Consider the following module:
{-# LANGUAGE MagicHash #-}
{-# OPTIONS_GHC -ddump-to-file -ddump-prep -O #-}
module FindIndex where
import GHC.Base (Int(I#), build)
import GHC.Prim
-- | The definitions of listToMaybe, findIndices and findIndex are taken from base
listToMaybe :: [a] -> Maybe a
listToMaybe [] = Nothing
listToMaybe (a:_) = Just a
findIndices :: (a -> Bool) -> [a] -> [Int]
findIndices p ls = build $ \c n ->
let go x r k | p x = I# k `c` r (k +# 1#)
| otherwise = r (k +# 1#)
in foldr go (\_ -> n) ls 0#
{-# inline findIndices #-}
findIndex :: (a -> Bool) -> [a] -> Maybe Int
findIndex p = listToMaybe . findIndices p
-- This is the definition of findIndices when USE_REPORT_PRELUDE is defined
findIndices' :: (a -> Bool) -> [a] -> [Int]
findIndices' p xs = [ i | (x,i) <- zip xs [0..], p x]
{-# inline findIndices' #-}
listToMaybe' :: [a] -> Maybe a
listToMaybe' = foldr (const . Just) Nothing
-- | using listToMaybe', we get a join point
findIndex2 :: (a -> Bool) -> [a] -> Maybe Int
findIndex2 p = listToMaybe' . findIndices p
-- | a "manual" implementaiton, we get a join point
findIndex3 :: (a -> Bool) -> [a] -> Maybe Int
findIndex3 p = go . zip [0..]
where
go [] = Nothing
go ((i, x) : xs)
| p x = Just i
| otherwise = go xs
-- | alternate version of findIndices, stock listToMaybe, no join point
findIndex4 :: (a -> Bool) -> [a] -> Maybe Int
findIndex4 p = listToMaybe . findIndices' p
-- | alternate version of findIndices, foldr listToMaybe, we get a join point
findIndex5 :: (a -> Bool) -> [a] -> Maybe Int
findIndex5 p = listToMaybe' . findIndices' p
Find attached .dump-prep files with ghc-8.2.1 and ghc-head at commit 8843a39b.
My interpretation of this is: with both ghc-8.2.1 and ghc-head, findIndex{2,4,5} get join points and findIndex{"",3} don't. Having a join point means constant stack space, not having a join point means linear stack space.
I don't understand the simplifier well enough to know whether ghc could do better here, but it seems that changing the definition of listToMaybe
to
listToMaybe :: [a] -> Maybe a
listToMaybe = foldr (const . Just) Nothing
would be a win. Are there any downsides?