[mercury-users] Set performance

[Peter Schachte]

On Mon, Jan 17, 2000 at 12:35:31PM +1100, Thomas Conway wrote:
> If people
> think it a good idea, I could add the predicate to the standard library.
> It would look like:
> 	:- pred union_list(list(set(T)), set(T)).
> 	:- mode union_list(in, out) is det.

How about a generalization of this that abstracts out the unioning.
Maybe a predicate something like

       :- pred list__fold_assoc(pred(T, T, T), list(T), T).
       :- mode list__fold_assoc(pred(in, in, out) is det, in, out) is det.

where if Op is associative, then

list__fold_assoc(Op, [First|Rest], List) <=>
	list_foldl(Op, Rest, First, List)

except that, eg, if the input list is [E1, E2, E3, E4, E5, E6], what
is computed is (I'll write this using functional notation since it's a
log clearer):

       Op(Op(Op(E1, E2), Op(E3, E4)), Op(E5, E6))

rather than

       Op(Op(Op(Op(Op(E1, E2), E3), E4), E5), E6)

It's the same number of applications of Op, and if Op is associative,
the results are the same, but Op will mostly be applied to elements of
the same "generation."  This will be more efficient if the complexity
of Op is determined by the size of the larger operand.


-- 
Peter Schachte                     I love deadlines. I like the whooshing
mailto:schachte at cs.mu.OZ.AU        sound they make as they fly by.
http://www.cs.mu.oz.au/~schachte/      -- Douglas Adams 
PGP: finger schachte at 128.250.37.3  


--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------