Ticket #1 (new enhancement)

Opened 8 years ago

Make Data.Map total

Reported by: conal Owned by: somebody
Priority: major Milestone:
Component: component1 Version:
Keywords: Cc:


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 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 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.

Note: See TracTickets for help on using tickets.