List.partition should be more lazy

[Bastiaan Heeren]

Using the function partition from the List module, a control stack overflow
occurs when evaluating the following expression:


     List> head $ fst $ partition even [1..]

     (35929 reductions, 63867 cells)
     ERROR: Control stack overflow


The definition of partition in both hugs and GHC libraries is:


     partition      :: (a -> Bool) -> [a] -> ([a],[a])
     partition p xs  = foldr select ([],[]) xs
                     where select x (ts,fs) | p x       = (x:ts,fs)
                                            | otherwise = (ts,x:fs)


The helper-function select is strict in its second argument because of the
pattern match on the tuple (ts,fs). Making the pattern match lazy by adding a ~
solves the problem!

        
     partition     :: (a -> Bool) -> [a] -> ([a],[a])
     partition p xs = foldr select ([],[]) xs
                    where select x ~(ts,fs) | p x       = (x:ts,fs)
                                            | otherwise = (ts,x:fs)
                                            

Cheers,
  Bastiaan