I'd still recommend Data.Map, since it's a much more efficient data structure for the task. Nick On Friday, August 24, 2012 11:44:16 PM Karl Voelker wrote:

On Fri, Aug 24, 2012 at 10:05 PM, Christopher Howard

wrote:

...

What is typically used in Haskell circles to provide associative array functionality? (I.e., key-value type arrays.) I'm not really looking for efficiency so much as interface convenience. Obviously I could code it myself based on lists or something, but I don't want to reinvent the wheel.

In simple situations, "coding it yourself" doesn't require much of any code, since the Prelude comes with a lookup function for lists of pairs:

lookup :: Eq a => a -> [(a, b)] -> Maybe b

-Karl V.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

On Sat, Aug 25, 2012 at 8:11 AM, Nick Vanderweit wrote:

I'd still recommend Data.Map, since it's a much more efficient data structure for the task.

Data.Map.lookup has better asymptotic time complexity than Prelude.lookup, but the relevant measures of efficiency depend on the situation. -Karl

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 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