Opened 10 years ago

Closed 9 years ago

Last modified 9 years ago

#3709 closed bug (fixed)

Data.Either.partitionEithers is not lazy enough

Reported by: daniel.is.fischer Owned by:
Priority: normal Milestone:
Component: libraries/base Version: 6.12.3
Keywords: Cc: bluescreen303@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Data.Either.partitionEithers gives a stack overflow for long or infinite lists.

Change

partitionEithers :: [Either a b] -> ([a],[b])
partitionEithers = foldr (either left right) ([],[])
 where
  left  a (l, r) = (a:l, r)
  right a (l, r) = (l, a:r)

to

partitionEithers :: [Either a b] -> ([a],[b])
partitionEithers = foldr (either left right) ([],[])
 where
  left  a ~(l, r) = (a:l, r)
  right a ~(l, r) = (l, a:r)

to make it lazy enough.

Example:

Data.Either> let fun k = case gcd k 15 of { 3 -> Left "Fizz"; 5 -> Left "Buzz"; 15 -> Left "FizzBuzz"; _ -> Right k }
Data.Either> take 10 . snd . partitionEithers $ map fun [1 .. 2*10^6 :: Integer]
*** Exception: stack overflow
Data.Either> take 10 . snd . lpartitionEithers $ map fun [1 :: Integer .. ]
[1,2,4,7,8,11,13,14,16,17]

Change History (4)

comment:1 Changed 10 years ago by malcolm.wallace@…

Resolution: fixed
Status: newclosed
Type of failure: None/UnknownRuntime performance bug

Fixed by

 * Data.Either.partitionEithers was insufficiently lazy.
 Ignore-this: 77e1b3288f66608c71458d8a91bcbe12

comment:2 Changed 10 years ago by igloo

This is a behavioural change, e.g.:

Main> case partitionEithers1 [Left 'a', error "Not me"] of (x : _, _) -> x

Program error: Not me

Main> case partitionEithers2 [Left 'a', error "Not me"] of (x : _, _) -> x
'a'

Shouldn't it be discussed on the libraries list first?

comment:3 Changed 9 years ago by bluescreen303

Cc: bluescreen303@… added
Resolution: fixed
Status: closednew
Version: 6.10.46.12.3

I just hit this bug on ghc 6.12.3 Found this ticket, and the suggested fix seems to work.

The state of this ticket was closed/fixed, and this was supposedly fixed 9 months ago. Hasn't the fix been merged into the 6.12 series?

comment:4 Changed 9 years ago by igloo

Resolution: fixed
Status: newclosed

No; it's in HEAD only, and will be in the upcoming 7.0 release.

Note: See TracTickets for help on using tickets.