v1.4.4

I just found and fixed bug #67, which seems serious enough to deserve a release.

v1.4.3

The most important change for v1.4.3 is that I have added a bunch of inline declarations which (koff koff) I should have added years ago. They improve performance on one update-heavy micro-benchmark by some 20% (on SBCL).

Another useful improvement is that I have added methods to the Slime Swank inspector for the FSet types (most of them, at least). I made one unusual design choice here, which is that if a collection is larger than a threshold size, it shows you a block of elements in the middle, with buttons to go either backward or forward. (Specifically, the buttons restrict the viewable range to the subrange above or below the displayed block, with, again, only a block in the middle of that viewable range actually displayed.) This lets you use binary search to reach an arbitrary element in a logarithmic number of clicks. I think this is greatly superior to always starting at the beginning and only showing you one more block per click, but others may find it a little odd at first. Let me know what you think.

If you use a different inspector and you want methods for that too, feel free to contribute them 😸 (Back in 2014, Camille Troillard contributed methods for the LispWorks inspector, but I haven't tried them myself.)

There's a new GMap result type map-to-sets, inspired by collate in this blog post. It can now be written functionally as:

(defun collate (items &key (key #'identity))
  (gmap (:result map-to-sets)
        (fn (item) (values (funcall key item) item))
        (:arg list items)))

Finally, I've added methods to support functional update on small lists. For instance:

> (defparameter *x* '(42 17 73))
> (defparameter *y* *x*)
> (incf (@ *x* 'second))
(42 18 73)
> *y*
(42 17 73)

These are methods on lookup and with, e.g.:

(defmethod lookup ((ls list) (key (eql 'first))) ...)
(defmethod with ((ls list) (key (eql 'first)) val) ...)

v1.4.2/Quicklisp 2024-10-12

This release contains a variety of small changes:

• new types replay-set and replay-map; these are sets and maps whose iteration order is the order in which elements/keys were originally added
• bug fixes: #18, #56, #57, #59, #61
• new functions proper-subset? and proper-subbag?
• the symbol :fset is now added to *features*
• there are now make-load-form methods for wb-set, wb-map, wb-seq, wb-bag, and dyn-tuple, permitting these to be dumped to fasl files
• new operation query-multi-restricted on list-relation

There is also a preliminary implementation of sets and maps using a new data structure, Michael Steindorfer's CHAMP. It is not fully built out yet, but most of the basics are there. I haven't benchmarked it fully either, but preliminary indications are that it will be much faster than the WB-trees, and comparable to the best that Clojure and Scala can offer. If you're feeling brave and want to take the new code for a test drive, you can create a CHAMP set or map with the new constructor macros ch-set and ch-map (these behave like the usual set and map). Do please let me know if you run into any problems. Many operations are not yet implemented on them, but I believe the ones that exist are well tested (on SBCL only) and debugged. Nonetheless, I am not yet recommending them for general use.

v1.4.1

The only change since v1.4.0 is that I updated the URL in fset.asd.

v1.4.0

Bug fixes and minor improvements. Highlights:

• I have moved all the docs to the FSet wiki on gitlab.common-lisp.net 🎉 and updated the link in the README.
• Issues fixed: #26, #28, #35, #40, #42, #44, #46. Although #44 was clearly a bug, I suppose there is a remote chance that some client out there is depending on the current behavior. Seems unlikely, though.
• More FSet operations also work on lists: with-first, with-last, contains?, filter.
• map-union and map-intersection now handle a val-fn result of :no-value, indicating that the result map should have no entry for the corresponding key.
• New modify macros set-differencef, map-unionf, map-intersectf.
• The query and query-multi operations on list-relation have a simplified API; the old API is still supported, but deprecated. (Is anyone using list-relation?) Instead of supplying a separate metapattern to indicate which pattern elements to search on, you just put fset::? in the pattern in uninstantiated locations.
• The API and internals of query-registry have been significantly revamped. Operations with-query and less-query are now with and less, and no longer take a metapattern; forward-key, lookup-restricted, and lookup-multi-restricted are all removed; and lookup-multi no longer has exponential time complexity (!). I'll be very surprised if anyone besides me is using this class, so I haven't bothered with backward compatibility here.

Many fixes from Paul Dietz

Paul Dietz wrote a lot of new tests and fixed many bugs. Highlights:

• Bugs in find, count-if, and disjoint? methods on sets
• Bugs in count-if method on bags
• Bugs in find, count-if, and compose methods on maps
• Bugs in position and position-if on seqs, when :from-end was true
• Also, a Clasp port by Karsten Poeck.

1.3.2: fix accumulated issues

Fixed or merged fixes for a few issues reported some time ago. Also fixed a couple of serious bugs in the 2-relation code.

I did back out a change that added methods on lookup and with on tuples and symbols. See PR#7 for discussion. There is a slight chance some code out there is using those methods, but it's best to fix it as it won't have been getting the desired performance anyway.