Proposal: Make intersect(By) lazier and faster
Bas van Dijk
v.dijk.bas at gmail.com
Thu Sep 16 12:10:36 EDT 2010
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
More information about the Libraries
mailing list