There’s a lot of detail in this chapter that you don’t need to know when you’re just getting started with FSet. So I’m giving you an advance TL;DR:
compare and hash-value.
It is possible to use your own comparison and hashing functions, but it’s rarely necessary.
Advanced users, along with language and library designers, will probably find this chapter worth reading closely; others might want to skip ahead, at this point, to the next chapter.
Most FSet collections are implemented in two ways. The original data structure I used was weight-balanced binary trees; this is an ordering-based implementation. More recently, I have added a hash-based data structure called CHAMP, which has better performance in most scenarios; the CHAMP implementations are now the default for sets, maps, and bags.
Both of these data structures are trees, that are functionally “updated” by path copying: given a point in the tree at which an update is to be applied, that node or leaf and all the nodes above it, up to and including the root, are copied, with the necessary change being applied to the copy. As such, operations on them have the same time complexities.