# List.partition should be more lazy

**Simon Peyton-Jones
**
simonpj@microsoft.com

*Fri, 23 Nov 2001 07:08:10 -0800*

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
*