Are people actually using the string argument for anything else than throwing an error message into the user's face? (I've always seen Either String as a bit of a hack)? If not, I think it would be best to leave fail to errors (as in IO), and desugar failed pattern matches to mempty/empty instead.