Why is partition no good list producer?

[Simon Peyton-Jones]

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 at haskell.org
[mailto:glasgow-haskell-users-
| bounces at haskell.org] On Behalf Of Jan Scheffczyk
| Sent: 25 February 2004 09:44
| To: glasgow-haskell-users at 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 at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users