On Thu, Feb 19, 2009 at 9:51 PM, Eugene Kirpichov wrote:

Greetings,

Is there a typeclass for mappings with a Data.Map-like interface, with stuff like: empty, insert, insertWithKey, unionWith etc. ? And, probably, a similar typeclass for mutable mappings like Data.Hashtable.

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

I'm asking mainly because I've been wondering why noone has yet written a mutable hashtable package with a MArray-like interface, I wrote a small thing myself and I am unsure as to what interface it should have.

Probably not adding anything terribly useful to this except to say that it'd be useful to me too - I've written a binding to a perfect hashing library (PerfectHash on hackage) which implements only 'fromList' and 'lookup', so a slightly more fine-grained type class hierarchy would be nice. (This particular implementation is useful when you have a lot of keys, but all known at run-time.) Mark -- A UNIX signature isn't a return address, it's the ASCII equivalent of a black velvet clown painting. It's a rectangle of carets surrounding a quote from a literary giant of weeniedom like Heinlein or Dr. Who. -- Chris Maeda

2009/2/19 Eugene Kirpichov :

Is there a typeclass for mappings with a Data.Map-like interface, with stuff like: empty, insert, insertWithKey, unionWith etc. ?

Maybe this is of interest: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gmap Peter

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