Proposal: Make intersect(By) lazier and faster
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.
More information about the Libraries