containers: specialize functions that fail in a Monad to Maybe

[ross]

Several functions on containers used to have types like

lookup :: (Ord k) => k -> Map k a -> Maybe a

but these were generalized to

lookup :: (Monad m, Ord k) => k -> Map k a -> m a

The only methods of Monad used are return and fail. The problem is that, depending on the monad, fail can be an ordinary value or a runtime error: this device makes it harder to check whether a program is safe, because it hides possible runtime errors among testable conditions.

The proposal is to change these signatures back, specializing them to Maybe.

The functions involved are:

lookup :: Ord k => k -> Map k a -> Maybe a
lookupIndex :: Ord k => k -> Map k a -> Maybe Int
minViewWithKey :: Map k a -> Maybe ((k,a), Map k a)
maxViewWithKey :: Map k a -> Maybe ((k,a), Map k a)
minView :: Map k a -> Maybe (a, Map k a)
maxView :: Map k a -> Maybe (a, Map k a)

lookup :: Key -> IntMap a -> Maybe a
maxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
minViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)
maxView :: IntMap a -> Maybe (a, IntMap a)
minView :: IntMap a -> Maybe (a, IntMap a)

minView :: Set a -> Maybe (a, Set a)
maxView :: Set a -> Maybe (a, Set a)

maxView :: IntSet -> Maybe (Int, IntSet)
minView :: IntSet -> Maybe (Int, IntSet)

No information is lost, because in each case there is a single failure mode.

[ross]

darcs patch

[ross]

Deadline: Mon 23rd June (4 weeks)

[ross]

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.

[ross]

oops, forgot to close it.