Re: [Caml-list] Choosing a random element in a Map or a Set

[jean-marc.alliot@irit.fr]

Thanks Simon. This works beautifully and without having to write a
single additional line of code. A few modifications were enough.

That's the advantage of getting old: 30 years ago I would have jumped on
my keyboard, now I realize that somebody smarter than me has probably
already solved the problem, and I just ask and wait...  😁

Also thanks to all the other people who have answered my request. It's a
pleasure, and an honor, to be still part of this community.

Le 18/03/2021 à 15:20, Simon Cruanes a écrit :
> There are some balanced trees with a weight attached to each node.
> I have an implementation in containers-data
> [signature](https://c-cube.github.io/ocaml-containers/3.2/containers-data/CCWBTree/module-type-S/index.html) .
>
> There is a random_choose function that does the traversal and exploits
> the weight to pick left/right for each node.
>
> I implemented this years ago but the comments say:
>
>     Most of this comes from "implementing sets efficiently in a functional language", Stephen Adams.
>     The coefficients 5/2, 3/2 for balancing come from "balancing weight-balanced trees"
>