[Haskell-cafe] A typeclass for Data.Map etc?

[wren ng thornton]

Eugene Kirpichov wrote:
> Looks like such a thing would be useful; as for now, I see at least
> two applications: Data.Map and Data.Trie (bytestring-trie) - it's a
> pity that they have rather similar interfaces, but the latter lacks
> many methods and some are named in a different way. 

Are there any particular functions you're missing? Most of the 
not-as-generic variants that Data.Map has are in Data.Trie.Convenience, 
so as to keep Data.Trie lean. There are a few notable exceptions which 
are on the todo list (the dual-use insert&lookup and update&lookup in 
particular).

In general I tried to keep all of the specific variants and any 
particularly helpful not-as-generic variants. Some of the not-as-generic 
variants didn't seem worth the time to wrapper given that we already 
have more generic variants (which Data.Map lacks) in Data.Trie and 
Data.Trie.Internal.


> Also, Data.Map has
> some inconsistensies, too: for instance, it has an insertWith' but
> lacks a unionWith'. "One typeclass for all" would eliminate these
> inconsistencies.

Some of the name changes were to overcome these inconsistencies (e.g. 
`findWithDefault` -> `lookupWithDefault`, since we have `lookup` and not 
`find`).


As for the original question, the gmap stuff and the Edison libraries 
provide some classes for this sort of thing. Last I checked the 
community hadn't really settled on what all should be included in such 
an interface (e.g. do you only have insert, delete, etc; or do you also 
require the very generic *By functions like Data.Trie? The former may 
not be helpful enough, and the latter may be too much of a burden on the 
instances.)

If (a) the community can agree on a typeclass for maps, which (b) allows 
instances to have a fixed type for keys (like Data.Trie and Data.IntMap 
have), (c) doesn't require ghc-only extensions like associated types, 
and (d) doesn't have onerous package dependencies, then I'd be more than 
happy to offer an instance. The #c requirement is basically a subset of 
#a I'd assume.

-- 
Live well,
~wren