Let 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 ++ ysThe resulting lists represent exactly the desired sets; repeated entries are permitted. Membership by sequential search makes
interR take time complexity in the worst case. The list concatenation in unionR costs to build its copied left spine and shares ys; fully enumerating the resulting list costs .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 time complexity, customarily written when both lengths are positive. Using the original xs for each membership test avoids searching an ever-growing output.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 ysWhen , sortedness proves that 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 ; equal heads are consumed together. Each step consumes at least one input head, so both have 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 | ||
| Unsorted, unique | ||
| Sorted, unique |
Articles by others on the same topic
There are currently no matching articles.