---

10.1 Features of FSet ¶

One thing I’ve tried to do in FSet is to choose names for functional update operations carefully. I recall reading once about newcomers to Java trying to use its BigInteger class, which is functional. They tended to expect an expression x.add(y) to mutate x to contain the sum, when it returns the sum instead. I contend that naming the operation plus instead of add would have largely prevented this confusion; people have written x + y since they were children in school, and no one thinks of that as somehow changing the value of x, whatever that would even mean in a mathematical context. (Java doesn’t support operator overloading, so literally making x + y work on BigInteger was not an available option; x.plus(y) is the closest one could get.)

Two important operations in FSet are named with and less; with adds an element or pair to a collection, while less removes one. These names come from SETL. Like plus, they are prepositions.

Naming things is always a matter of tradeoffs. Good names make code understandable by carrying the right connotations, but names also need to be reasonably familiar words, and for common operations, not too long. I wouldn’t go so far as to say that all functional update operations should be named by prepositions, but I do think that, other things being equal, prepositions and nouns tend to be better choices than verbs, and verbs that don’t connote mutation are better than those that do. In a couple of cases, where the obvious names insert and splice strongly connote mutation, I have used their past participles (inserted and spliced) instead of their base forms. (Honesty compels me to admit that this is a recent change; I have not, historically, adhered to my own desideratum as well as I would have liked. But I still recommend it.)

Here are some other functional collections libraries and the names they use for operations like with and less:

Library	with (on sets/on maps)	less (on sets/on maps)	notes
Clojure core	conj / assoc	disj / dissoc
Racket	hash-set	hash-remove	1
Scala	incl / updated	excl / removed	2
Haskell	insert	delete	3
SML/NJ	add / insert	subtract / remove
Pyrsistent (Python)	add / set	remove
RPDS (Rust)	insert	remove

Notes:

1. Only maps (hash tables) are provided. Racket uses the popular Scheme convention that names of mutating operations end in !; someone familiar with that convention should be able to guess that these are functional updates.
2. Here we see a use of past participles.
3. Of course, there’s no ambiguity here since anyone writing Haskell knows it’s a pure functional language.

A lot of these sound to me like verbs of mutation, with Clojure and Scala being the two languages that seem to have gone to some effort to avoid those.

Another area where I would hold FSet up as an example is space efficiency. I wanted to support client programs that use many small collection instances, as well as those that use large collections. Two things I have done to reduce space overhead are:

• It’s not uncommon for people to implement maps first, then reuse the implementation for sets, by wrapping it with a set API that uses only the map key slots; the value slots are still allocated, but don’t contain anything important. FSet sets are implemented separately from maps, so they don’t waste this space.
• The WB-tree implementations, including that of seqs, use heterogeneous trees: instead of having tree nodes all the way down to the leaves, they keep the lowest two to four levels of the tree in bounded-length vectors. This saves a lot of space on small collections; for example, an 8-element set made entirely of tree nodes would take an estimated 37 words, but in FSet, it’s just 11 words, assuming no alignment padding.

Turning to semantic features, FSet has several that I would recommend to language and library designers:

• Defaults associated with maps and seqs. This not a difficult feature to add; the only complications show up in operations like map-union that arguably need to do something sensible with the defaults of their operands (though, simply ignoring them might be a viable option).
• Quasi-mutating operators, on the other hand, are likely to require language support; few languages are designed in such a way that they could be added as a library.
• Bags, though not as commonly used as maps or sets, are still handy often enough to deserve inclusion in a comprehensive collections library. Although these can be implemented as just a wrapper around maps, FSet has separate implementations for them, so as to be able to track both the bag size (the total of the multiplicities) and the set size (the number of unique elements) for every subtree.
• Binary relations are another type that are useful enough to be worth implementing.
• Left preference is a property of operations such as union that combine two collections into a third in some way. It says that when the two operands contain distinct objects that are nonetheless equal according to the applicable comparison function, and one of those objects is used in the result, the one in the result will always be the one that came from the left operand. The Haskell library also makes this guarantee.
• Allowing comparison functions to implement a strict weak ordering, instead of requiring (or at least assuming) a total ordering, is perhaps a more controversial design choice. There is a small amount of overhead associated with allowing for the possibility of equivalent-but-unequal elements; the feature is not completely free. For Common Lisp, it is arguably a necessity, if only because of the admittedly rare case of uninterned symbols with the same name (but I have seen macros generate such symbols in the wild; the concern is not academic). In other languages, you (or rather, your users) can probably live without it the vast majority of the time, but I wonder whether there might not be rare exceptions. None of the other ordered-tree collections implementations I have looked at allow strict weak orderings, though.