On 20 May 2004 07:50, Adrian Hey wrote:
On Wednesday 19 May 2004 10:47 am, Simon Marlow wrote:
I'm happy for this to be "the" Data.Trees.AVL library. I'm sure others will want to comment on the details. I wonder whether it would make sense to have a specialised AVLMap type, which would let you optimise the representation of AVL-based finite maps?
Do you mean a newtype wrapper for the current AVL type or distinct algebraic type which contains both the key and the associated value as separate fields (like the Map type folks were talking about recently)?
If you mean the former, one thing I was thinking about doing was creating an AVL based clone of the current Data.FiniteMap library so folk could experiment with the effect of using both on real programs just by changing their imports.
Actually I meant the latter, but this is a good idea too. Data.Map.AVL?
If you mean the latter, I'm not keen on this because it would mean duplication of a lot of code for the new type, and I'm not sure that it would be an optimisation at all. I considered this but decided against it on the grounds that I suspect a major contributor to the true cost of tree operations is heap burn rate. The AVL tree type has only 3 fields in each constructor (not 5 as with the Map type for example), and the code was carefully written to avoid unnecessary heap construction wherever possible. Doing this would result in 4 fields in each constructor.
The total space overhead for the tree would be smaller, because the pair constructor is inlined. 5 words per tree node instead of 7, and one fewer eval each time you examine a node. However if a lot of rebalancing happens on the tree, then being able to share the key/value pairs might be a win. Code duplication is clearly a problem, though. Anyway, t'was just a thought...
I'd also like to book "Data.COrdering" too, if that's OK.
Data.COrdering is less obviously the right thing. Can you give some motivation for the design here?
Because you you generally do end up combining values which turn out to be "equal", in some manner. If you don't use a function which returns a COrdering, then you have to either..
Pass the comparison and combining function separately down your recursive search or whatever. But this will have extra runtime overhead, which is often unnecessary since the only time the combining function is ever used is when the comparison returns EQ.
or..
Use some default combining function (like pairing) and apply the real combining function later. But pairing is the only reasonable default combining function I can think of, and this not always the right type (e.g. for pushing elements in a tree or set union), and even when it's OK type wise you've still got the overhead of an additional map operation (e.g for set intersection). You could get around the type problem using lists I suppose, and use (++) as the default combining function, but this doesn't seem very attractive to me.
Right, I think I see the reasoning. In the case of writing/pushing, the COrdering allows you to pass a composition of a comparison and a combining function around, which looks cleaner. It's not obviously more efficient than passing the two functions around, because the actual comparisons will be going through an extra level of higher-order function (except that you've INLINEd everything in sight, so the COrdering combinators probably disappear :-). In the case of lookup, it doesn't look like you need COrdering: just apply the "combining function" to the result of genRead/genTryRead, right? But given that you're using COrdering for writes, using it for read too is reasonable. Ok, I guess I'm more or less convinced. Cheers, Simon