= Solution
Let $m,n$ be the two input lengths and suppose numeric comparisons cost constant time. The <list-based set representation> determines which <representation invariant> each answer must preserve.
For unsorted <lists> allowing repetition, retain every left-hand occurrence whose value appears on the right for <set intersection>, and use <list concatenation> for <set union>:
``
interR xs ys = [x | x <- xs, x `elem` ys]
unionR xs ys = xs ++ ys
``
The resulting <lists> represent exactly the desired <sets>; repeated entries are permitted. Membership by <sequential search> makes `interR` take $O(mn)$ <time complexity> in the worst case. The <list concatenation> in `unionR` costs $O(m)$ to build its copied left spine and shares `ys`; fully enumerating the resulting <list> costs $O(m+n)$.
For unsorted, duplicate-free inputs, the same intersection keeps uniqueness, while the union retains `xs` and appends only right-hand elements absent from `xs`:
``
interU xs ys = [x | x <- xs, x `elem` ys]
unionU xs ys = xs ++ [y | y <- ys, not (y `elem` xs)]
``
Neither filtered <list> has internal repetitions, and the filter in `unionU` also excludes overlap with `xs`. Both operations have worst-case $O(mn+m+n)$ <time complexity>, customarily written $O(mn)$ when both lengths are positive. Using the original `xs` for each membership test avoids searching an ever-growing output.
For sorted, duplicate-free <lists>, compare only the two current heads:
``
interS [] ys = []
interS xs [] = []
interS (x:xs) (y:ys)
| x < y = interS xs (y:ys)
| x > y = interS (x:xs) ys
| otherwise = x : interS xs ys
unionS [] ys = ys
unionS xs [] = xs
unionS (x:xs) (y:ys)
| x < y = x : unionS xs (y:ys)
| x > y = y : unionS (x:xs) ys
| otherwise = x : unionS xs ys
``
When $x<y$, sortedness proves that $x$ cannot occur anywhere in the right <list>, so it can be discarded from the <set intersection> or immediately emitted to the <set union>. The symmetric argument handles $y<x$; equal heads are consumed together. Each step consumes at least one input head, so both have $O(m+n)$ worst-case <time complexity>. These bounds assume the sorted <representation invariant> is already established; sorting arbitrary inputs has its own cost.
|| Representation
|| <Set intersection>
|| <Set union>, including output traversal
| Unsorted, repetitions allowed
| $O(mn+m+n)$
| $O(m+n)$
| Unsorted, unique
| $O(mn+m+n)$
| $O(mn+m+n)$
| Sorted, unique
| $O(m+n)$
| $O(m+n)$
Back to article page
