Bringing the IntMap API up to par with the Map API
wren ng thornton
wren at community.haskell.org
Thu Aug 19 16:54:59 EDT 2010
Johan Tibell wrote:
> On Thu, Aug 19, 2010 at 3:41 AM, wren ng thornton <
> wren at community.haskell.org> wrote:
>> Johan Tibell wrote:
>>> I've created a proposal to add a strict left fold, see separate email. In
>>> the process of doing so I've discovered that the whole foo/fooWithKey
>>> duplication is unnecessary, at least from a performance perspective.
>>> It's probably not feasible to remove the duplication from e.g. the
>>> API, but it's worth keeping in mind when designing data structure APIs in
>>> the future.
>> For something like Data.Map, the API is definitely redundant (though we may
>> wish to keep the simplified versions around in Data.Map.Convenience or the
>> like). And even though Data.IntMap is technically a trie, it'd probably be
>> fine without them too--- since the keys are of fixed size, and can be
>> combined with bit twiddling instead of rearranging memory.
> The keys are actually stored in the leaves in the IntMap keys so what I said
> about Map applies to IntMap as well.
Ah yes, that's true. (Though even if it weren't...)
More information about the Libraries