Lists intersection, subtraction, difference

import Data.List (sort)

-- |Finds lists intersection. O(2nlogn + 2n)
intersection :: Ord a => [a] -> [a] -> [a]
intersection = iter intersectF

intersectF :: Eq a => (Maybe a, Maybe a) -> [a] -> [a]
intersectF (Just x, Just y) acc = if x == y then x:acc else acc
intersectF _ acc = acc

-- |Subtracts second list from the first. O(2nlogn + 2n)
subtraction :: Ord a => [a] -> [a] -> [a]
subtraction = iter subtractF

subtractF :: Eq a => (Maybe a, Maybe a) -> [a] -> [a]
subtractF (Just x, Just y) acc = if x /= y then x:acc else acc
subtractF (Just x, Nothing) acc = x:acc
subtractF _ acc = acc

-- |Finds symmetric difference between lists. O(2nlogn + 2n)
difference :: Ord a => [a] -> [a] -> [a]
difference = iter diffF

diffF :: Eq a => (Maybe a, Maybe a) -> [a] -> [a]
diffF (Just x, Just y) acc = if x /= y then x:y:acc else acc
diffF (Just x, Nothing) acc = x:acc
diffF (Nothing, Just y) acc = y:acc
diffF _ acc = acc

-- |Iterates two sorted lists at once.
-- Concrete behavior is incapsulated in the supplied function. O(n)
iter :: Ord a => ((Maybe a, Maybe a) -> [a] -> [a]) -> [a] -> [a] -> [a]
iter f xs ys = foldr f [] (join (sort xs) (sort ys))

-- |Joins two sorted lists into list of pairs similarly to SQL full join. O(n)
join :: Ord a => [a] -> [a] -> [(Maybe a, Maybe a)]
join xs ys = join' xs ys []
  where join' [] [] acc = acc
        join' (x:xs) [] acc = join' xs [] ((Just x, Nothing):acc)
        join' [] (y:ys) acc = join' [] ys ((Nothing, Just y):acc)
        join' allXs@(x:xs) allYs@(y:ys) acc =
          let (x', y', xs', ys') = case x `compare` y of
                EQ -> (Just x, Just y, xs, ys)
                GT -> (Nothing, Just y, allXs, ys)
                LT -> (Just x, Nothing, xs, allYs)
          in join' xs' ys' $ (x', y'):acc