[Haskell-beginners] Creating Indexes

[Christopher Reichert]

On Sun, Dec 14 2014, martin <martin.drautzburg at web.de> wrote:
> Hello all,
>
> I recently wrote a Haskell program, which accesses Lists extensivly. That was okay to verify the overall idea, but
> performance degraded rapidly when I made the lists bigger. There was a quadratic effect and this was not surprizing,
> given the nature of the code.
>

Are you certain this was because of the List and not something else?

If you are constantly doing lookups on lists then, indeed, performance
will suffer.

> I am somewhat aware of Haskell types which offer faster access. But they all seem to assume that I know the way data is
> accessed when I write the type. A new access path may force me to rededign the type.
>
> What I am looking for is something which behaves like indexes in a RDBMS, i.e. to define a list-like type on an innocent
> data type (like a tuple) and then add indexes as needed. Is there such a thing?


Would an association list fit the model you are talking about?


ghci> let al = [ (1, "hello"), (2, "world") ]
ghci> Prelude.lookup 1 al
Just "hello"
ghci> Prelude.lookup 3 al
Nothing


You can then transform to Map (and back) easily:

ghci> Data.Map.fromList al
fromList [(1,"hello"),(2,"world")]
ghci> Data.Map.insert 42 "foo" $ fromList al
fromList [(1,"hello"),(2,"world"),(42,"foo")]



See Real World Haskell (http://book.realworldhaskell.org/read/data-structures.html):



--
Christopher Reichert
irc: creichert
gpg: C81D 18C8 862A 3618 1376  FFA5 6BFC A992 9955 929B
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 818 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20141214/ddbb1829/attachment.sig>