Proposal: Make intersect(By) lazier and faster

Daniel Fischer daniel.is.fischer at web.de
Thu Sep 16 11:21:42 EDT 2010


With the current implementation of intersectBy, the calculation of
intersectBy _ xs []
takes O(length xs) time, hence doesn't finish on infinite lists and 
evaluates to _|_ for partial lists xs (... : _|_).
The proposed new implementation,

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, returning [] also for infinite or partial xs.
The first equation retains the property

intersectBy _ [] _|_ = []

Trac ticket: http://hackage.haskell.org/trac/ghc/ticket/4323

Period of discussion: Two weeks, until 30 Sep. 2010.

Cheers,
Daniel


More information about the Libraries mailing list