id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc
1	Make Data.Map total	conal	somebody	"`Data.Map k` is a `Functor` but not an `Applicative` or a `Monad` because it lacks `pure`/`return`.
If there were a `pure v`, the resulting map would have to map ''every'' key to `v`, to be consistent with the meaning of maps as functions.
(See ''[http://conal.net/papers/type-class-morphisms Denotational design with type class morphisms]''.)
However, such a map is not partial, and hence not finite.

To fix this algebraic awkardness, I suggest we simplify `Data.Map` to be ''total'' but still based on finitely many values.
The fix is very simple: give every map an explicit default value, by means of `pure`.
The `lookup` operation has a simpler type: `lookup :: Ord k => k -> Map k a -> a` (but let's ''please'' reverse the arguments, so that `lookup` is the semantic function).
Note the absence of `Maybe` in the result.

Both the current and suggested interface are trivially easy to implement in terms of the other.
Represent the  partial `Map k v` as the total `Map k (Maybe v)`.  (Really `First` in place of `Maybe`, as explained below.)
Represent the total as the partial map and a default value.

This new `Map` type can now be in `Functor`, `Applicative`, `Monad`, and `Monoid`.
Thanks to `Applicative`, it can also inhabit the numeric classes.
The semantics of all of these instances are directly determined by type class morphisms (TCMs), which says that methods on maps must behave consistently with the same methods on the meaning of maps.
In particular, the `Monoid` instance relies on `v` being a `Monoid` (by TCM, since the function/semantics monoid is defined that way).
For instance, `v` can be a `Maybe`, `First`, or `Last`, which all give different and useful ways to combine maps, rather than the one policy for `union` (which corresponds to the `First` monoid).

See Section 3 of ''[http://conal.net/papers/type-class-morphisms Denotational design with type class morphisms]'' for more details and context.

I have ''not'' gone through the whole `Data.Map` API to see the implications this proposal beyond what I've mentioned above."	enhancement	new	major		component1