There's a lot more missing: Test for disjointness, subset-relation as well as instances for Show and Ord (lexical order, not subset-relation). Also FiniteMap should have these instances (also for Eq), if the elements have. These instances would allow nested sets and maps.
Since you had difficulties to supply an instance Ord for FiniteMap (see below), here is my proposal: instance (Ord key, Ord elt) => Ord (FiniteMap key elt) where fm_1 <= fm_2 = if sizeFM fm_1 == sizeFM fm_2 -- quick test (unnecessary) && keysFM fm_1 == keysFM fm_2 then eltsFM fm_1 <= eltsFM fm_2 else keysFM fm_1 <= keysFM fm_2 -- or "<" if you wish That - besides Set - FiniteMap is an instance of Eq may almost be obvious but wasn't documented! ("show . fmToList" for "Show" would be enough for me.) Cheers Christian The sources "/ghc-5.02.2/hslibs/data/FiniteMap.lhs" showed: instance (Eq key, Eq elt) => Eq (FiniteMap key elt) where fm_1 == fm_2 = (sizeFM fm_1 == sizeFM fm_2) && -- quick test (fmToList fm_1 == fmToList fm_2) {- NO: not clear what The Right Thing to do is: instance (Ord key, Ord elt) => Ord (FiniteMap key elt) where fm_1 <= fm_2 = (sizeFM fm_1 <= sizeFM fm_2) && -- quick test (fmToList fm_1 <= fmToList fm_2) -}