To summarize: Several container classes have types like lookup :: (Monad m, Ord k) => k -> Map k a -> m a and use fail to signal exceptional conditions. This allows them to be used with a range of monads, e.g. [], IO and parser monads. Some of these use the string passed to fail. However the strings are not very useful, and probably shouldn't be exposed in production code: Data.Map.lookup: Key not found Data.Map.lookupIndex: Key not found Data.Map.minViewWithKey: empty map Data.Map.maxViewWithKey: empty map Data.Map.minView: empty map Data.Map.maxView: empty map The problem with this device is that depending on the monad, fail can be an ordinary value, an exception or a runtime error (the default). It complicates checking whether a program is safe, because it hides possible runtime errors among testable conditions. The proposal was to revert these types to the simpler lookup :: (Ord k) => k -> Map k a -> Maybe a No information would be lost, as each of these functions has only one use of fail -- the Maybe type describes the situation precisely. As the initial "thing with zero and return", it can be lifted to any other. Several people argued that the non-Maybe case is rare, and explicitly marking use of a different monad is no bad thing. Changing the monad classes is not a possibility at this stage: we need to work with the classes as defined in Haskell 98. No-one defended the status quo, but Twan van Laarhoven and Dan Doel argued that if the constraint were changed from Monad to MonadPlus, one should be able to assume a safe fail, while avoiding the the need for lifting. At present, fail in STM and Seq use the default error, which could be changed. Haskell 98 specifies the fail in IO as throwing an exception (the MonadPlus instance is in the mtl package). In favour of the proposal were: apfelmus, Conor McBride, David Menendez, Don Stewart, Duncan Coutts, Iavor Diatchki, Isaac Dupree, Josef Svenningsson, Krasimir Angelov, Lennart Augustsson, Neil Mitchell, Ross Paterson. That's not consensus, but it is a substantial majority, and I think we've explored all the issues. So I propose to make the change.