Blogger - HTIF - join

-- |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