It is my pleasure to announce the first release of `baby`

.

`baby`

is an OCaml library that offers several implementations of balanced binary search trees. At this time, `baby`

offers a replacement for OCaml’s `Set`

module; it does not yet have a replacement for OCaml’s `Map`

module.

Height-balanced and weight-balanced binary search trees are offered out of the box. Furthermore, to advanced users, the library offers a lightweight way of implementing other balancing strategies.

The following points offer a comparison between `baby`

and OCaml’s `Set`

library.

## Better Performance

At the time of writing, `baby`

offers generally better performance than OCaml’s `Set`

library. Its operations are generally faster (sometimes much faster; sometimes slightly faster; sometimes slightly slower) than those of the `Set`

library, and its memory allocation rate is slightly lower.

## Constant-Time Cardinal

In contrast with the `Set`

library, `baby`

’s weight-balanced trees offer a `cardinal`

function whose time complexity is *O(1)*. They also offer a family of random access functions (`get`

, `index`

, etc.) whose time complexity is *O(log n)*. Furthermore, by exploiting cardinality information, the functions `subset`

and `equal`

are sometimes able to return `false`

in constant time.

## Better Sharing

`baby`

’s binary operations (`union`

, `inter`

, `diff`

) take advantage of (and preserve) physical equality in a more aggressive way. This allows them to (sometimes) be faster and allocate less memory.

## Adaptive Conversions To Sets

`baby`

’s conversion functions `of_list`

, `of_array`

, and `of_seq`

have adaptive complexity. If the input data is sorted, their complexity is *O(n)*; otherwise, their complexity gracefully degrades down to *O(n.log n)*.

## More Operations

`baby`

offers a few operations that do not exist in OCaml’s `Set`

library:

- The symmetric difference,
`xor`

; - The conversion functions
`of_array`

and`to_array`

; - The extremum-removal functions
`remove_min_elt`

and`remove_max_elt`

; - The enumeration API in the submodule
`Enum`

. Enumerations should be slightly faster than standard sequences, and are able to efficiently seek ahead, via the function`from`

.

## Documented Complexity

In `baby`

, the time complexity of every operation is documented.

## Compatibility

`baby`

is perfectly compatible with OCaml’s Set library. In other words, using `Baby.W.Set`

instead of `Set`

is safe.

As a word of warning, though, if the equivalence relation on elements is coarser than equality (that is, if `compare x y = 0`

does not imply `x = y`

), then `Baby.W.Set`

and `Set`

might behave differently when a choice must be made between two equivalent elements. This can occur in `union`

, `of_list`

, `of_array`

, `of_seq`

, `add_seq`

, `map`

.