Opened 7 years ago

Closed 7 years ago

#4323 closed proposal (fixed)

Change implementation of intersectBy

Reported by: Owned by:
Priority: normal Milestone: Not GHC
Component: libraries/base Version: 6.12.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


Currently, intersectBy eq xs [] takes O(length xs) time to calculate and returns _|_ on (x : _|_). The proposed change,

intersectBy             :: (a -> a -> Bool) -> [a] -> [a] -> [a]
intersectBy _  [] _     =  []
intersectBy _  _  []    =  []
intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]

makes this an O(1) operation and returns [] for infinite or partial (... : _|_) lists xs. The first equation is necessary to retain intersectBy _ [] _|_ = [].

Attachments (1)

intersect.dpatch (48.4 KB) - added by 7 years ago.
Updated patch

Download all attachments as: .zip

Change History (5)

comment:1 Changed 7 years ago by

Period of discussion: two weeks, until 2010/09/30.

Changed 7 years ago by

Attachment: intersect.dpatch added

Updated patch

comment:2 Changed 7 years ago by

Status: newpatch

The proposal was supported by Bas van Dijk and Thomas Schilling, no objections were raised. Mailing list thread

Please review and merge.

comment:3 Changed 7 years ago by igloo

Milestone: Not GHC

comment:4 Changed 7 years ago by igloo

Resolution: fixed
Status: patchclosed

Patch applied, thanks.

Note: See TracTickets for help on using tickets.