Brent wrote a nice reply to my last post about infinite set operations. I agree that the arbitrary halting threshold embedded in my solution is imperfect. This post further expands upon Brent’s suggested approach.
What if we redefine the difference and intersection operations as functions that emit information about the comparisons that they perform as they move through both inputs? In this case we can use (Maybe a), producing a Nothing when we reject an item, and a (Just a) when an item is accepted.
This stream of (Maybe a) values could then be filtered by another function to produce a result appropriate for the application at hand.
> module InfiniteSets2 where > import List > import Maybe
First we redefine the difference function.
> infDiff2 :: (Eq a, Ord a, Enum a) => [a] -> [a] -> [Maybe a] > infDiff2 [] _ = [] > infDiff2 (x:xs) [] = (Just x):(infDiff2 xs []) > infDiff2 (x:xs) (y:ys) | x == y = Nothing : (infDiff2 xs ys) > | x < y = (Just x) : (infDiff2 xs (y:ys)) > | otherwise = infDiff2 (x:xs) ys
And here is the intersection function.
> infIntersect2 :: (Eq a, Ord a, Enum a) => [a] -> [a] -> [Maybe a] > infIntersect2 [] _ = [] > infIntersect2 _ [] = [] > infIntersect2 (x:xs) (y:ys) | x == y = (Just x) : (infIntersect2 xs ys) > | x < y = Nothing : (infIntersect2 xs (y:ys)) > | otherwise = Nothing : (infIntersect2 (x:xs) ys)
We can rewrite our old infDiff function, here renamed to nDiff, as
follows.
> nDiff n l1 l2 = f $ map (catMaybes . (take n)) (tails $ infDiff2 l1 l2) > where f [] = [] > f ([]:xs) = [] > f (x:xs) = (head x) : (f xs)
And here are some example calls.
> test1 = take 20 $ infDiff2 [1,2,3,5,10,20,50,100] [1,3,4,6,10,15,30,50] > test2 = take 20 $ infDiff2 [3,5..] [3,5..] > test3 = take 20 $ infDiff2 ([1,2] ++ [3,5..]) [3,5..] > test4 = take 20 $ infDiff2 [1,3..] [2,4..] > test5 = take 20 $ infDiff2 ([1,2] ++ [3,5..]) [3,5..25] > test6 = take 20 $ infIntersect2 [1,2,3,5,10] [1,3,4,6,10] > test7 = take 20 $ infIntersect2 [3,5..] [3,5..] > test8 = take 20 $ infIntersect2 [3,5..] [2,4..] > testNDiff1 = take 40 $ nDiff 5 ([1,2] ++ [3,5..]) [3,5..]
