At work we newtype Map in a manner analogous to Data.Set.NonEmpty.NonEmptySet, copying the API of Data.Map.Internal without empty and dealing with partial functions by returning Maybe (NonEmptyMap k v).
I'm curious if there's any interest in adding such a type to this package.