Yes, if partition was implemented as described in the Report, namely as two independent filters, then both would be good producers. But then it would not be a good consumer (because it would consume the list twice). In the GHC library it is implemented as a single traversal producing two lists, so it's a good consumer but not a good producer. I don't know how to do both at once. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users- | bounces@haskell.org] On Behalf Of Jan Scheffczyk | Sent: 25 February 2004 09:44 | To: glasgow-haskell-users@haskell.org | Subject: Why is partition no good list producer? | | Hi all, | | I'm about to optimize a fairly large Haskell program, which uses | partition quite often (and a fold immediately afterwards). | The GHC User guide section about RULE pragmas says that filter is a | good producer, whereas partition is not mentioned (therefore, I | assume it is not). | | I put a little test program together: | | > fuse1 :: [Bool] -> (Bool,Bool) | > fuse1 xs = (x,y) | > where (fs,gs) = partition id xs | > x = foldr (&&) True fs | > y = foldr (||) False gs | | > fuse2 :: [Bool] -> (Bool,Bool) | > fuse2 xs = (x,y) | > where fs = filter id xs | > gs = filter not xs | > x = foldr (&&) True fs | > y = foldr (||) False gs | | Compiling it via ghc -O and loading the compiled object to ghci | results in: | | Prelude Test> fuse2 (replicate 10000000 False) | (True,False) | (8.19 secs, 241174592 bytes) | Prelude Test> fuse1 (replicate 10000000 False) | (*** Exception: stack overflow | (6.18 secs, 48472660 bytes) | | | I understand the results: Using partition an intermediate list seems | to be build. | But WHY? | | Is it simply because of a missing RULE pragma for partition or is | there a "deeper" reason? | | Cheers, | Jan | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users