outerJoin.hs

import Data.List (sortBy)
import Data.Function (on)

merge :: [(Int, a)] -> [(Int, b)] -> [(Maybe a, Maybe b)]
merge az bz = case (az, bz) of
    ((i, a) : az', (j, b) : bz') -> 
        case i `compare` j of
            LT -> (Just a, Nothing) : merge az' bz
            EQ -> (Just a, Just b)  : merge az' bz
            GT -> (Nothing, Just b) : merge az  bz'

    (az, []) -> [(Just a, Nothing) | (_, a) <- az]
    ([], bz) -> [(Nothing, Just b) | (_, b) <- bz]

outerJoin :: [(Int, a)] -> [(Int, b)] -> [(Maybe a, Maybe b)]
outerJoin az bz = sort az `merge` sort bz
  where
    sort = sortBy (compare `on` fst)

test = outerJoin 
    [(i, i) | i <- [0,2..100]]
    [(i, i) | i <- [0,3..100]]