alt-stdlib: Ticket #1: Make Data.Map total
http://trac.haskell.org/alt-stdlib/ticket/1
<p>
<tt>Data.Map k</tt> is a <tt>Functor</tt> but not an <tt>Applicative</tt> or a <tt>Monad</tt> because it lacks <tt>pure</tt>/<tt>return</tt>.
If there were a <tt>pure v</tt>, the resulting map would have to map <i>every</i> key to <tt>v</tt>, to be consistent with the meaning of maps as functions.
(See <i><a class="ext-link" href="http://conal.net/papers/type-class-morphisms"><span class="icon">Denotational design with type class morphisms</span></a></i>.)
However, such a map is not partial, and hence not finite.
</p>
<p>
To fix this algebraic awkardness, I suggest we simplify <tt>Data.Map</tt> to be <i>total</i> but still based on finitely many values.
The fix is very simple: give every map an explicit default value, by means of <tt>pure</tt>.
The <tt>lookup</tt> operation has a simpler type: <tt>lookup :: Ord k => k -> Map k a -> a</tt> (but let's <i>please</i> reverse the arguments, so that <tt>lookup</tt> is the semantic function).
Note the absence of <tt>Maybe</tt> in the result.
</p>
<p>
Both the current and suggested interface are trivially easy to implement in terms of the other.
Represent the partial <tt>Map k v</tt> as the total <tt>Map k (Maybe v)</tt>. (Really <tt>First</tt> in place of <tt>Maybe</tt>, as explained below.)
Represent the total as the partial map and a default value.
</p>
<p>
This new <tt>Map</tt> type can now be in <tt>Functor</tt>, <tt>Applicative</tt>, <tt>Monad</tt>, and <tt>Monoid</tt>.
Thanks to <tt>Applicative</tt>, 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 <tt>Monoid</tt> instance relies on <tt>v</tt> being a <tt>Monoid</tt> (by TCM, since the function/semantics monoid is defined that way).
For instance, <tt>v</tt> can be a <tt>Maybe</tt>, <tt>First</tt>, or <tt>Last</tt>, which all give different and useful ways to combine maps, rather than the one policy for <tt>union</tt> (which corresponds to the <tt>First</tt> monoid).
</p>
<p>
See Section 3 of <i><a class="ext-link" href="http://conal.net/papers/type-class-morphisms"><span class="icon">Denotational design with type class morphisms</span></a></i> for more details and context.
</p>
<p>
I have <i>not</i> gone through the whole <tt>Data.Map</tt> API to see the implications this proposal beyond what I've mentioned above.
</p>
en-usalt-stdlibhttp://trac.haskell.org/alt-stdlib/chrome/common/trac_banner.png
http://trac.haskell.org/alt-stdlib/ticket/1
Trac 0.11.1