Alexander Dunlap wrote:
The way I see it, we have a few options. We could introduce some type classes to cover the various container operations and ask all Platform packages to only use operations from these classes, where applicable.
Depending on what exactly you mean by "applicable", there are worse efficiency problems than large dictionaries. Speaking on behalf of Data.Trie, there are a number of functions that can be offered on tries which give large asymptotic improvements over naive/generic functions on maps. In general the efficiency of tries is comperable with maps, the whole point of using tries is to be able to use these special functions which aren't available to maps. This problem isn't unique to tries, it's the major reason why there are so many container types out there. For instance, the snoc function can be defined for [] but it's not a good idea to use it frequently; snoc on Data.Sequence, however, is perfectly fine to use often. While it'd be nice to have some type classes to make it easier for client code to be polymorphic in the container type, we should be wary of putting too much faith in it. When there are asymptotic or large-constant differences depending on the container, this needs to be made clear to clients and users. This isn't just polymorphism over the representation type, it's polymorphism over *algorithms*. This is a major source of performance problems and confusion in OOP languages, which do provide such generic interfaces. For a language like Haskell the computational complexity of functions belongs to the API and is as important as the type signature and pragmatic properties. One thing that may help though is if we could agree on what functions should belong to such an interface and how they should be named. The bytestring-trie package took after Data.Map and Data.IntMap, though there's been much contention over the names and the order of arguments since then. Having a coherent set of guidelines (specialized to sequence and map structures) would probably help more than technical changes. -- Live well, ~wren