I found that I often need predecessor and successor of some key in Data.Map.Map. Just like that: predKey, succKey :: Ord k => Data.Map.Map k a -> k -> Maybe k predKeyElem, succKeyElem :: Ord k => Data.Map.Map k a -> k -> Maybe (k,a) Data.Map has operations like that on key indexes, but it is slightly unnatural to work with three entities (index, key and element) where two suffices. So I propose to include those operations into next version of Data.Map. If anyone could point me in the right direction I could do any necessary modifications myself (just because I need it).