instance Ord FiniteMap

[Alastair Reid]

Johannes Waldmann <joe@isun.informatik.uni-leipzig.de> writes:
> I find that I use Set and FiniteMap rather for reasons of clarity in
> coding.  This is what `you guys in industry' call `academic
> programming', right :-) If speed is really an important issue, then
> one would have to resort to some kind of hash table lookup anyway.

In defence of FiniteMap...  If you build your lookup table all in one
go, a hash might be best.  If you add elements continually throughout
the run of your program and need to do lookups in both early and late
versions of the tree, you may get better memory usage with a
finitemap.  And if your lookup table is really a list of nested scopes
most containing just a few symbols (e.g., a typical compiler lookup
table) you might even get on better with a simple linked list.  IIRC,
GHC's lookup tables switch mode according to size: they start as
linked lists; then become finitemaps; then become hash tables (or
something like that - it was a long time ago that I saw this).

Which is all to say that you should hide your choice of data structure
behind a common API and change it as you run into performance
problems.


-- 
Alastair Reid        reid@cs.utah.edu        http://www.cs.utah.edu/~reid/