Hi, Am Mittwoch, den 10.02.2016, 20:07 +0000 schrieb Lana Black:
I tested maximumBy with foldl, and it runs in constant memory for lists, so extra strictness won't have any benefits in this particular case. The following snippet clearly shows it.
----- main = print $ maximumBy compare [1..100000000000]
-- Copied from Data.Foldable with foldl1 replacing foldr1. maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a maximumBy cmp = foldl1 max' where max' x y = case cmp x y of GT -> x _ -> y
Thanks for testing, but I’d be careful with small examples. It is not unlikely that GHC can “fully grasp” them and do wonders, possibly even fusing the lists, but with larger examples we’d get bad behavior. And indeed, with "-O0", or with NOINLINE maximumBy, I very quickly fill my memory. Too bad there is no foldl1' to easily verify that with that, we get the desired behavior even without -O. Now this gets interesting. I’m wondering if there is a good way of implementing foldl1', so I looked at the default implementation of foldl1, which is: foldl1 :: (a -> a -> a) -> t a -> a foldl1 f xs = fromMaybe (error "foldl1: empty structure") (foldl mf Nothing xs) where mf m y = Just (case m of Nothing -> y Just x -> f x y) This implements foldl1 via foldl and an accumulator _wrapped in a Maybe and case-analized in every step_. I sincerely hope that every instance overrides this by an more efficient version. And at least those Foldable instances with more than one element in Data.Foldable do... Nevertheless, for the question of memory usage, a generic definition will do. And indeed, using foldl1' :: Foldable t => (a -> a -> a) -> t a -> a foldl1' f xs = fromMaybe (error "foldl1': empty structure") (foldl' mf Nothing xs) where mf Nothing y = Just y mf (Just x) y = x `seq` Just (f x y) in your example, I get constant memory consumption as expected. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • https://www.joachim-breitner.de/ XMPP: nomeata@joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org