Containers in the Haskell Platform

[wren ng thornton]

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