On Thu, Sep 16, 2010 at 5:21 PM, Daniel Fischer
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@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