Re: [Caml-list] Set union/inter/diff efficiency

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> Does anyone have any ideas or references on how the union/inter/diff
> functions of the Set module could be optimised by accepting a
> sequence of sets rather than a pair at a time ?

No.

> For example, if A overlaps B overlaps C but A does not overlap C
> then it is probably quicker to compute the union "(A U C) U B"
> rather than "A U B U C".

I remember having discussed with Jean-Christophe Filliâtre of the
[compare] implementation of Xavier Leroy. He noticed that it was a
smart lazy linearization of both sets.

In other words you can see it as if one had put a zipper on each set
and one calls when needed the [next] function.

A = 3 -> 5 -> 6 -> 7 -> 10
B = 3 -> 6 -> 8 -> 13

You can say that A < B at the second call of [next]

I suppose you could do a similar thing for union and intersection with
several sets

A = 3 -> 5 -> 6 -> 7 -> 10
B = 3 -> 6 -> 8 -> 13
C = 2 -> 4 -> 5 -> 6

You can call [next] in such a way that the pointers "jump" to an
interesting point. Here, it would be something like

max/min = 3
C -> 4 (first integer >= 3)
max/min = 4
A -> 5 (first integer >= 4)
max/min = 5
B -> 6 (first integer >= 5)
max/min = 6
C -> 6 (...)
A -> 6 (...)
=> output 6 in the intersection

> Better still, does anyone have a replacement Set module which
> implements this functionality?

I am not aware of any in Caml, SML or Haskell but I may be wrong.


        Diego Olivier