@ 型に依存する部分だけ型クラスで分ければよいのではないでしょうかね?
empty :: (Ord a, h ~ LeftistHeap x) => h a
empty = E
isEmpty :: (Ord a, h ~ LeftistHeap x) => h a -> Bool
isEmpty E = True
isEmpty _ = False
insert :: (Ord a, h ~ LeftistHeap x, Heap h) => a -> h a -> h a
insert x h = merge (T 1 x E E) h
find :: (Ord a, h ~ LeftistHeap x) => h a -> Maybe a
find E = Nothing
find (T _ x _ _) = Just x
delete :: (Ord a, h ~ LeftistHeap x, Heap h) => h a -> Maybe (h a)
delete E = Nothing
delete (T _ _ a b) = Just (merge a b)
class Heap h where
merge :: Ord a => h a -> h a -> h a
instance Heap (LeftistHeap Min) where
merge h E = h
merge E h = h
merge h1@(T _ x a1 b1) h2@(T _ y a2 b2)
= if x <= y
then makeT x a1 $ merge b1 h2
else makeT y a2 $ merge h1 b2
instance Heap (LeftistHeap Max) where
merge h E = h
merge E h = h
merge h1@(T _ x a1 b1) h2@(T _ y a2 b2)
= if x >= y
then makeT x a1 $ merge b1 h2
else makeT y a2 $ merge h1 b2