I'll happily incorporate the code if someone sends me a patch... Cheers, Simon
-----Original Message----- From: Hal Daume III [mailto:hdaume@ISI.EDU] Sent: 29 May 2002 15:03 To: Johannes Waldmann Cc: GHC Users Mailing List Subject: Re: instance Ord FiniteMap
I agree; the problem is that I fear that making my own instance by using setToList will be very inefficient (or at least much more so than an instance which actually looks at the tree structure).
-- Hal Daume III
"Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
On Wed, 29 May 2002, Johannes Waldmann wrote:
for instance, Sets of Sets of things would be really nice.
Sure. One could simply use lexicographic ordering (i. e. s1 `compare` s2 = setToList s1 `compare` setToList s2) or length-lexicographic ordering (for efficiency) ... = (cardinality s1, setToList s1) `compare` (cardinality s2, setToList s2)
As you write, there seems to be no reason not to do this. An Ord instance should be a linear ordering, and the above are. -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
setToList will be very inefficient (or at least much more so than an instance which actually looks at the tree structure).
this would be much more difficult to design, since one and the same set may be represented by quite different trees: they might have been created by inserting elements in different order, triggering different re-balancings. 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 the above case, using setToList shouldn't be that much of a problem: given two `average' sets (of course there is no such thing, but anyway), there is good chance that they differ in one of the smaller elements, so the list of nodes (of the tree representing the set) would only be evaluated to a small extent. -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
Johannes Waldmann
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/
participants (3)
-
Alastair Reid -
Johannes Waldmann -
Simon Marlow