{- 
respor.hs:38:12:
    Couldn't match expected type `a' against inferred type `b'
      `a' is a rigid type variable bound by
          the type signature for `join' at respor.hs:36:18
      `b' is a rigid type variable bound by
          the type signature for `join' at respor.hs:36:30
    In the second argument of `(==)', namely `y'
    In the expression: x == y
    In a stmt of a pattern guard for
                 the definition of `join':
          x == y
-}

import Data.Maybe
import Data.List

class (Ord a) => Joinable a where
    key	:: a ->	String

data Foo = Foo { fooKey :: String, fooVal :: Int }
instance Eq Foo where
    x == y = (key x) == (key y)
instance Ord Foo where
    compare x y
        | x == y  = EQ
        | (key x) <= (key y) = LT
        | otherwise = GT
instance Joinable Foo where
    key	(Foo k _) = k

data Baz = Baz { bazKey :: String, bazVal :: Int }
instance Eq Baz where
    x == y = (key x) == (key y)
instance Ord Baz where
    compare x y
        | x == y  = EQ
        | (key x) <= (key y) = LT
        | otherwise = GT
instance Joinable Baz where
    key	(Baz k _) = k


singleMerge :: Maybe Foo -> Maybe Baz -> Maybe Foo
singleMerge (Just f) (Just b) =	Just ( f { fooVal = bazVal b } )

merge :: [Foo] -> [Baz] -> [Foo]
merge fs bs = catMaybes $ map (uncurry singleMerge) $	join (sort fs) (sort bs)

join :: (Joinable a, Joinable b) => [a] -> [b] -> [(Maybe a, Maybe b)]
join (x:xs) (y:ys)
     | x == y = (Just x, Just y) : join xs ys
     | x <= y = (Just x, Nothing) : join xs (y:ys)
     | x >= y = (Nothing, Just y) : join (x:xs) ys