> module Intersect where

> import FiniteMap
> import Set

Problem given to students of CAS 781 ``Functional Programming''
on 2003-03-19:

Define a function

> intersection :: Ord a => [a] -> [a] -> [a]

that calculates the intersection of two possibly infinite argument
lists.

More generally, define

> intersection2 :: (Ord a, Ord b, Ord c) =>
>                  [(a,b)] -> [(a,c)] -> [(a,(Set b, Set c))]

that produces the pairs consisting of keys occurring in both
potentially infinite argument lists and pairs of sets of the
respectively accompanying values, as observed so far.


The original motivation for this problem
was the possible use of intersection2 (and intersection)
in the context of confluence questions:
Both functions could be hooked into the breadth-first
generation functions.

Implementation:

> intersection = h1 emptySet emptySet
>  where
>   h1 s1 s2 (x:xs) ys = (if x `elementOf` s2 && not (x `elementOf` s1)
>                         then (x:)
>                         else id
>                        ) $ h2 (addToSet s1 x) s2 xs ys
>   h1 s1 s2 [] [] = []
>   h1 s1 s2 [] ys = h2 s1 s2 [] ys

>   h2 s1 s2 xs (y:ys) = (if y `elementOf` s1 && not (y `elementOf` s2)
>                         then (y:)
>                         else id
>                        ) $ h1 s1 (addToSet s2 y) xs ys
>   h2 s1 s2 xs [] = h1 s1 s2 xs []

It is possible to prove that the result is a list of unique elements
which comprese exactly the intersection between the sets of elements
of the two argument lists.

> test1 p q = intersection [p,p+p ..] [q,q+q ..]


> intersection2 = undefined  --- for you to fill in the definition!


> intersection2' :: (Ord a, Ord b) => [(a,b)] -> [(a,b)] -> [(a,([b], [b]))]
> intersection2' ps qs = map h $ intersection2 ps qs
>  where
>   h (x,(rs,ss)) = (x,(setToList rs, setToList ss))

Material for testing intersection2:

> list2 p mp = zip (map (`mod` mp) [p,p+p..]) [1..]
> test2 p mp q mq = intersection2' (list2 p mp) (list2 q mq)

> v1 = cardinality $ mkSet $ map fst $ take 10000 $ test2 97 1000 101 1000