Add `SORTED` and associated navigators

[IGJoshua]

One navigator which seems relatively easy to implement and which is lacking from the existing ones is navigating to a sorted sequence.

I've written three navigators for this and am ready to provide a PR, but the contributing document recommended making an issue to see if the improvement fits within the purview of specter.

The three navigators I'd like to see added are SORTED, which navigates to a sorted view of the current sequence as if calling clojure.core/sort on it, sorted, which is the same but takes a comparator function, and sorted-by, which takes a specter path as a keypath as well as an optional comparator.

All three navigators provide both selection and transformation, and my current implementation keeps items in order based on the index they are at in the resulting sequence, with new items being concatenated onto the end.

This is more or less a discussion issue about whether or not these navigators fit within specter, and what their exact semantics should be, before I open a PR with that implementation and tests for it.

[nathanmarz]

This sounds interesting to pursue. What are the semantics of SORTED when the a value exists multiple times in the input sequence?

[IGJoshua]

The semantics of sort are stable, that is equal items are not reordered. The current way I've implemented SORTED will first create an intermediate sequence of pairs of an objects' original index into the sequence and the object itself, and then it's sorted by the object, split into two sequences, one of the indices, and one of the objects. The objects are passed on to next-fn, and the results are then paired with the indices and sorted by the index, before pouring the objects back into an empty collection of the same type as the input sequence.

(let [sorted (sort-by second (map-indexed vector structure))
      indices (map first sorted)
      results (next-fn (map second sorted))
      unsorted (sort-by first (map vector indices results))]
  (into (empty structure)
        (map second)
        unsorted))

What this means though is that the semantics of SORTED with multiple equal items is that the navigated-to sequence will have multiple equal objects as well, and the order will be the same between the input and navigated-to sequences by way of identical?.

[nathanmarz]

This sounds worth adding to Specter – please open a PR. I sent a contributor agreement to your email for signature.

[IGJoshua]

Alright, I've signed the contributor agreement, I'll have a draft PR with the implementation up later today, and I'll be adding tests to it soon.