Containers in the Haskell Platform
wren ng thornton
wren at community.haskell.org
Thu Aug 6 23:36:20 EDT 2009
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.
More information about the Libraries