associative arrays

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

associative arrays

Christopher Howard
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.

--
frigidcode.com
indicium.us

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 554 bytes
Desc: OpenPGP digital signature
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120824/9843e5d2/attachment.pgp>

Reply | Threaded
Open this post in threaded view
|

associative arrays

Patrick Redmond
I think that you're looking for Data.Map. Here's the docs:
http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.4.2.1/Data-Map.html
It's discussed on LYaH too:
http://learnyouahaskell.com/making-our-own-types-and-typeclasses

On Sat, Aug 25, 2012 at 1:05 AM, Christopher Howard <
christopher.howard at frigidcode.com> 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.
>
> --
> frigidcode.com
> indicium.us
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120825/cf36b3e1/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

associative arrays

Karl Voelker
In reply to this post by Christopher Howard
On Fri, Aug 24, 2012 at 10:05 PM, Christopher Howard
<christopher.howard at frigidcode.com> 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.


Reply | Threaded
Open this post in threaded view
|

associative arrays

Nick Vanderweit
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
>
> <christopher.howard at frigidcode.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners


Reply | Threaded
Open this post in threaded view
|

associative arrays

Adrien Haxaire-2
 On Sat, 25 Aug 2012 09:11:30 -0600, Nick Vanderweit wrote:
> I'd still recommend Data.Map, since it's a much more efficient data
> structure
> for the task.

 They are implemented as a tree, which is fine as long as you do not
 want/need duplicates in your association list.

 They are also well documented and the extensive API will do most of
 what you'll need. I use them a lot.


--
 Adrien Haxaire
 www.adrienhaxaire.org | @adrienhaxaire


Reply | Threaded
Open this post in threaded view
|

associative arrays

Karl Voelker
In reply to this post by Nick Vanderweit
On Sat, Aug 25, 2012 at 8:11 AM, Nick Vanderweit
<nick.vanderweit at gmail.com> 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


Reply | Threaded
Open this post in threaded view
|

associative arrays

Dmitry V'yal
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.
>

Can you please elaborate a bit? I suspect lists better when there are
just a few elements, but how much is a "few"? And what's about storage
efficiency? How big is (Data.Map.fromList [1])?


Reply | Threaded
Open this post in threaded view
|

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