List.partition should be more lazy

[Simon Peyton-Jones]

It was wrong in the Haskell report too (now fixed; see my home page).
Also fixed in GHC 5.02.

Simon

| -----Original Message-----
| From: Bastiaan Heeren [mailto:bastiaan@cs.uu.nl]=20
| Sent: 23 November 2001 13:55
| To: haskell@haskell.org
| Subject: List.partition should be more lazy
|=20
|=20
| Using the function partition from the List module, a control=20
| stack overflow occurs when evaluating the following expression:
|=20
|=20
|      List> head $ fst $ partition even [1..]
|=20
|      (35929 reductions, 63867 cells)
|      ERROR: Control stack overflow
|=20
|=20
| The definition of partition in both hugs and GHC libraries is:
|=20
|=20
|      partition      :: (a -> Bool) -> [a] -> ([a],[a])
|      partition p xs  =3D foldr select ([],[]) xs
|                      where select x (ts,fs) | p x       =3D (x:ts,fs)
|                                             | otherwise =3D (ts,x:fs)
|=20
|=20
| The helper-function select is strict in its second argument=20
| because of the pattern match on the tuple (ts,fs). Making the=20
| pattern match lazy by adding a ~ solves the problem!
|=20
|        =20
|      partition     :: (a -> Bool) -> [a] -> ([a],[a])
|      partition p xs =3D foldr select ([],[]) xs
|                     where select x ~(ts,fs) | p x       =3D (x:ts,fs)
|                                             | otherwise =3D (ts,x:fs)
|                                            =20
|=20
| Cheers,
|   Bastiaan=20
|=20
|=20
| _______________________________________________
| Haskell mailing list
| Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
|=20