Use foldr in place of explicit recursion and toList#162
Use foldr in place of explicit recursion and toList#162vrom911 merged 2 commits intokowainik:masterfrom
Conversation
|
@josephcsible Thanks for your work! However, I would love to be sure that this change is safe and doesn't introduce unexpected performance penalties before merging the PR. |
|
Hi @josephcsible! Let me know if you're interested in implementing benchmarks (in a separate repository) to see whether your PR changes the performance of those functions 🙂 |
|
Yes, I plan to do that. I would've by now, but I've been distracted by other things. |
|
@josephcsible No worries! Take your time 🙂 |
|
Hey @josephcsible , sorry for bothering, do you have plans for this PR? |
|
Thanks for the reminder; this slipped off my radar. A quick test seems to indicate that the new {-# LANGUAGE RankNTypes #-}
import Control.Monad (when)
import Data.Foldable (toList)
import System.Environment (getArgs)
allM_toList :: (Foldable f, Monad m) => (a -> m Bool) -> f a -> m Bool
allM_toList p = go . toList
where
go [] = pure True
go (x:xs) = do
q <- p x
if q then go xs else pure False
allM_foldr :: (Foldable f, Monad m) => (a -> m Bool) -> f a -> m Bool
allM_foldr p = foldr go (pure True)
where
go x acc = do
q <- p x
if q then acc else pure False
testAllM :: (forall f m a. (Foldable f, Monad m) => (a -> m Bool) -> f a -> m Bool) -> IO ()
testAllM allM = do
print $ allM Just (replicate 50000000 True)
print $ allM Just (replicate 50000000 True ++ [False])
print $ allM id (replicate 50000000 (Just True) ++ [Nothing])
main :: IO ()
main = do
args <- getArgs
when ("toList" `elem` args) $ do
putStrLn "Using the toList variant"
testAllM allM_toList
when ("foldr" `elem` args) $ do
putStrLn "Using the foldr variant"
testAllM allM_foldrAnd the results: |
|
@josephcsible Wow, great news! Looks like it's indeed much better than the previous implementation 👍 In that case, it would be indeed nice to have this feature merged. |
vrom911
left a comment
There was a problem hiding this comment.
Amazing result! Thanks for your hard work, @josephcsible 👍
Checklist:
HLint
hlint.dhallaccordingly to my changes (add new rules for the new imports, remove old ones, when they are outdated, etc.)..hlint.yamlfile (see this instructions).General
stylish-haskellfile.[ci skip]text to the docs-only related commit's name.