Skip to content

Draft: FSet2

This MR introduces FSet version 2! 🚀 🚀 The big change for v2 is that the CHAMP data structures are now used by default for sets, maps, and a few other types (see the CHAMP MR). There are some other API changes as well, mostly having to do with the treatment of defaults in maps and seqs.

Background: After using FSet myself for a while, I came to feel that the way I had made the map and seq defaults work was in some ways still infelicitous. This especially came out when using map-union, map-intersection, and compose of a map with a function. The inconvenience was that every map had a default, and the lambda expressions I was writing to process the map values were also being called on the defaults, which were generally nil, so those lambda expressions had to handle nil explicitly. I found this inelegant, and decided that FSet should distinguish the case of a nil default from that of not having a default at all. So now, these two cases are distinct.

To minimize disruption to existing clients, I have created a new package fset2: which exports its own versions of the relevant symbols. With some hopefully-minor exceptions noted below, existing clients will not see any changes in semantics. To get the new behavior, change :use fset in your package definitions to :use fset2 (similarly change the :shadowing-import-from fset clause, if you use it) and recompile.

However, one change you will see, even if you're not using the new package, is to the printed representation of maps and seqs. Previously, if the default was nil, no suffix was printed; any other default would be printed after the map or seq, preceded by a slash. Now, in the common case where the default is nil, you will see an explicit /NIL; the suffix is omitted only when there is no default.

The CHAMP-related changes are these:

  • The default implementations for set and map are now ch-set and ch-map respectively. The WB versions are still available, of course, for cases when you want the collection to be maintained in a particular order.
  • For some less-commonly-used collections — replay-set, replay-map, 2-relation, and list-relation — I have taken the risk of changing them to use CHAMP by default in the fset package, without introducing separate fset2: names. For the replay sets and maps, it's hard to see any reason to prefer the WB implementations, since the iteration order is externally imposed anyway. For the relations, I'm skeptical that anyone uses them but me, though I could be wrong. If this change impacts you, please speak up; I could be persuaded to limit this change to FSet2.

The default-related changes are these:

  • Unless you explicitly specify another default, the default for maps and seqs is still nil. However, you can obtain a map or seq with no default by supplying :no-default to the constructor macro (map etc.) or :no-default? t to the constructor function (empty-map etc.)
  • Doing lookup on a map with no default, giving a key not mapped by the map, signals an error of class map-domain-error, a subclass of lookup-error.
  • An out-of-bounds access on a seq with no default signals an error of class seq-bounds-error; first or last on an empty seq with no default signals an error of class empty-seq-error. Both of these are also subclasses of lookup-error.
  • Tuple keys also still have a default of nil. You can create a tuple key with no default by passing :no-default? t to define-tuple-key or get-tuple-key; and doing lookup on a tuple using a key with no default, if the tuple has no value for that key, signals an error of class tuple-key-unbound-error (also a subclass of lookup-error).
  • map-union, map-intersection, and compose detect when a map has no default, and avoid calling the passed function on the default in that case. (There is also a change to the default-related behavior of map-difference-2, but this is less important).

Detailed list of changes

Constructor macros set, map, replay-set, replay-map, and 2-relation now construct CHAMP collections.

Constructor macros map, wb-map, wb-custom-map, ch-map, ch-custom-map, replay-map, wb-replay-map, wb-custom-replay-map, ch-replay-map, and ch-custom-replay-map can be made to create a collection with no default by including :no-default somewhere in the argument list.

Constructor functions empty-wb-set, empty-ch-set, empty-wb-bag, empty-map, empty-wb-map, empty-ch-map, empty-seq, empty-wb-seq, empty-wb-replay-set, empty-ch-replay-set, empty-replay-map, empty-wb-replay-map, empty-ch-replay-map, empty-wb-2-relation, empty-ch-2-relation, empty-list-relation, empty-wb-list-relation, and empty-ch-list-relation have all had their parameters changed from optional to keyword parameters. empty-map, empty-wb-map, empty-ch-map, empty-seq, empty-wb-seq, empty-replay-map, empty-wb-replay-map, and empty-ch-replay-map can be made to create a collection with no default by passing :no-default? t.

Generic function without-default can be used to remove the default from a map, seq, or replay-map.

The way map-union, map-intersection, map-difference-2, compose, and image handle defaults has changed:

  • For map-union, the previous behavior (since 1.4.0) was to call the supplied val-fn on the defaults for the two maps unless those defaults were both nil. (The pre-1.4.0 behavior was to call val-fn on the defaults unconditionally.) The new behavior is to call val-fn on the defaults only when both maps have defaults; if only one has a default, that becomes the default of the result; if neither map has a default, the result has no default.
  • For map-intersection, the previous behavior (both pre- and post-1.4.0) was the same as for map-union. The new behavior is to call val-fn on the defaults only when both maps have defaults; otherwise, the returned map has no default.
  • For map-difference-2, the previous behavior was to simply copy the default of each argument map to its respective return value. The new behavior is to do that unless both maps have defaults and those defaults are equal.
  • For compose, the previous behavior was to apply the second argument (which can be a map or a function) to the first argument's default. The new behavior is to do that only if the first argument has a default; if it doesn't, the result doesn't either.
  • For image where the second argument is a map, the previous behavior is that the result would have the same default as that argument. The new behavior is that the result has no default. (We can't call the function to compute a new default, as might have seemed consistent with these other operations, because in this case, the function is called with both a domain and range value, and there's no specific domain value corresponding to the default. My guess is that this operation, as I've defined it, is not very useful anyway; compose is probably the better choice for most use cases.)

The lookup operation on a bag (most commonly invoked using the @ macro) now returns the multiplicity as its first value, rather than a boolean. (If you want a boolean result, use contains?.)

The name identity-ordering-mixin is no longer exported; it was already deprecated in favor of identity-equality-mixin.

There are some changes related to dynamic tuples. def-tuple-key', which was deprecated in favor of define-tuple-key', is no longer exported. Macro define-tuple-key' now has keyword parameters, including no-default?; if a key has no default and a lookup is done with it on a tuple that has no value for that key, an error will be signaled. (The default default is still nil.) The behavior that if the default were a function, it would be invoked on the tuple to compute the value returned by lookup, has been removed. Function get-tuple-key, which can be used programmatically to obtain a tuple key, also now has keyword parameters defaultandno-default?`, and will also now update the default on an existing key (bug fix).

The rank operator takes an ordered collection — here a wb-set, wb-bag, or wb-map — and a value. If the value is in the collection (for a map, if it is a key), then rank returns an integer giving its position within the ordering. You might think that if the value were not in the collection, rank would return the position it would have if it were added; but for some reason I don't recall, I defined it to return one less than that. FSet2 fixes this; rank now returns the position it would have if it were added.

FSet2 now exports functions compare-lists-lexicographically, compare-strings-lexicographically, compare-vectors-lexicographically, and compare-seqs-lexicographically, which may be useful as custom orderings for the WB collections.

A function instance-class-name has been added to help with comparing and hashing classes that have subclasses.

The old-syntax GMap result-types :set, :seq, :wb-seq, :map, :wb-map, :ch-map, :map-to-sets, and :concat no longer work, because they would be ambiguous between FSet1 and FSet2 semantics. Use the appropriate new-syntax form: :arg set, :result set, etc. (See section 2.4 of the Misc-Extensions README.) Also, result-type fset2:map-to-sets now uses CHAMP sets and maps.

Edited by Scott L. Burson

Merge request reports

Loading