On Sun, Dec 14 2014, martin
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