Friday, May 09, 2014

[hagimlse] insertWith0 and overloading functions

We propose the following addition to Data.Map, a function that inserts (f new_value zero) if the key is not found, or (f new_value old_value) if the key is found. That is, following semantics, but it ought to be implemented more efficiently than a separate lookup and insert:

insertWith0 :: Ord k => (a -> b -> b) -> b -> k -> a -> Map k b -> Map k b;
insertWith0 f zero key new_value old_map = Map.insert key (f new_value $ fromMaybe zero $ Map.lookup key old_map) old_map;

The naming scheme between insertWith0 and insertWith is vaguely analogous to foldr and foldr1. The motivation was a Map of lists, where multiple values get cons'd to head of the list:

cons_in_map :: Ord k => k -> a -> Map k [a] -> Map k [a];
cons_in_map = insertWith0 (:) [];

We would also like insertWithKey0 fromWith0 fromWithKey0. However, this makes even more "crowded" the already crowded API to Data.Map. We would prefer to avoid the situation of Java, where it is impossible to program without always having a library reference handy. Is there a better way of organizing the library?

One possibility is overloaded functions. A single function, say, named insert, is overloaded with the functionality of insert insertWith insertWithKey insertWith0 insertWithKey0 (and maybe more) and the desired function is invoked by the inferred type, or if necessary an explicit expression type signature at the call point of insert. Perhaps also overload with the arguments in several possible orders.

Previous thoughts on overloaded functions. A discussion about FlexibleInstances including a brief mention of how Text.Printf pulls off function overloading: http://stackoverflow.com/questions/8998915/implement-function-overloading-in-haskell

1 comment:

Anders Kaseorg said...

insertWith0 f zero key new_value = Map.alter (Just . f new_value . fromMaybe zero) key