Proposal: Make intersect(By) lazier and faster

[Bas van Dijk]

On Thu, Sep 16, 2010 at 5:21 PM, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
> 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
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>

+1

However I like using a 'filter' more than using a list comprehension:

intersectBy          :: (a -> a -> Bool) -> [a] -> [a] -> [a]
intersectBy _  [] _  = []
intersectBy _  _  [] = []
intersectBy eq xs ys = filter (\x -> any (eq x) ys) xs

Hopefully this definition can even benefit from foldr/build fusion
using the filter RULES in GHC.List:

{-# NOINLINE [0] filterFB #-}
filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b
filterFB c p x r | p x       = x `c` r
                 | otherwise = r

{-# RULES
"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr
(filterFB c p) n xs)
"filterList" [1]  forall p.     foldr (filterFB (:) p) [] = filter p
"filterFB"        forall c p q. filterFB (filterFB c p) q = filterFB c
(\x -> q x && p x)
 #-}

Regards,

Bas