Hi, Martin try ixset [0]. But as you said, a simple data structure is not enough for your use case, as any "mere" data structure has some concrete performance characteristics. Something more abstract is needed. [0] http://hackage.haskell.org/package/ixset On Mon, Dec 15, 2014 at 7:20 AM, martin wrote:

Am 12/14/2014 04:41 PM, schrieb Christopher Reichert:

...

On Sun, Dec 14 2014, martin wrote:

...

Hello all,

I recently wrote a Haskell program, which accesses Lists extensivly.

...

...

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

That was okay to verify the overall idea, 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?

Well I *have* an association list, however with more than one column by which I lookup rows (relationally spreaking). I know I can use Maps, but I cannot convert to a map for every lookup, because it will be more expensive than just taversing the list.

I can also just use Maps all along, but this requires I settle for one key column (or a combination of columns). When the necessity arises to lookup by new criteria (other columns) I would have to redesign the map or add another map or whatever. In any case it is very different to adding an index in a RDBMS. _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Carl Eyeinsky