Why is partition no good list producer?

[Jan Scheffczyk]

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