[Haskell-beginners] Creating Indexes

[martin]

Am 12/14/2014 04:41 PM, schrieb 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?


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.