[Haskell-beginners] associative arrays

[Patrick Redmond]

> On 29.08.2012 10:19, Karl Voelker wrote:
>> Data.Map.lookup has better asymptotic time complexity than
>> Prelude.lookup, but the relevant measures of efficiency depend on the
>> situation.

On Wed, Aug 29, 2012 at 2:25 AM, Dmitry Vyal <akamaus at gmail.com> wrote:
> Can you please elaborate a bit? I suspect lists better when there are just
> a few elements, but how much is a "few"?

I believe that Prelude.lookup looks through the list until it finds
the thing you're looking for or exhausts the list [this is something
like O(n)]. Data.Map performs a binary search over its tree [this is
something like O(log n)]

> And what's about storage
> efficiency? How big is (Data.Map.fromList [1])?

A map associates keys and values, so your example doesn't actually
work. As for space efficiency, I'm sure that an association tree and
an association list are simple enough that both grow linearly with the
number of elements.

Prelude> :m +Data.Map
Prelude Data.Map> let x = fromList [("banana", ["yellow"]), ("apple",
["green", "red"]), ("tomato", ["red"])]
Prelude Data.Map> x
Prelude Data.Map> Data.Map.lookup "apple" x
Just ["green","red"]
Prelude Data.Map> Data.Map.lookup "fish" x
Nothing