Haskell is, to my knowledge, the most widely used pure functional language.
As one might expect, Haskell is well supplied with functional collections. I found sets, maps, and
sequences in a Containers package, bags in a Multiset package, and binary relations in a Relation
package. All these are implemented as weight-balanced trees except for the sequences, which are 2-3
finger trees. Other implementations are probably available, though; there are over 17,000 packages
on hackage.haskell.org. I didn’t find anything like FSet’s replay sets and maps, but maybe I
just don’t know what the package is called.
All of the types I found seem to be generously supplied with operations. Very impressive!
I did notice a few minor differences between FSet’s approach and Haskell’s. These are not all criticisms of Haskell, and even if they were, they would be quite minor; FSet and Haskell clearly have considerable overlap in our philosophies.
The idea of a default associated with a map doesn’t seem to have occurred to them. Data.Map
has several lookup operations: lookup which returns a Maybe to handle the missing-key
case; !, which errors on a missing key; and findWithDefault, that lets you supply a
default at lookup time.
They have several flavors of map union. unionWith is closest to FSet’s map-union,
though it doesn’t require or assume an idempotent value-combining function; the potential
optimization by doing so doesn’t seem to have occurred to them. They have map intersection and
difference as well, and even the map difference has a flavor that accepts a combining function.
Their map type has a map operation, which FSet calls compose; amusing that they use
the word “map” in both senses. mapWithKey corresponds to FSet’s map-image.
Their union and intersection operations, on both sets and maps, implement left preference. As I said — there’s lots of commonality here.
On the whole, I’d say FSet still has a little bit to teach Haskell, but also quite a lot to learn from it.