<< Back to previous view

[CLJ-428] subseq, rsubseq enhancements to support priority maps? Created: 20/Aug/10  Updated: 05/Jul/15

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Backlog
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Stuart Halloway Assignee: Unassigned
Resolution: Unresolved Votes: 2
Labels: None

Attachments: Text File clj-428-code-v5.patch     Text File clj-428-tests-v5.patch    
Patch: Code and Test


See dev thread at http://groups.google.com/group/clojure-dev/browse_thread/thread/fdb000cae4f66a95.

Excerpted from Mark Engelberg's message of July 14, 2010 in that discussion thread:

It will only be possible to properly implement subseq on priority maps with a patch to the core. subseq achieves its polymorphic behavior (over sorted maps and sorted sets) by delegating much of its behavior to the Java methods seqFrom, seq, entryKey, and comparator. So in theory, you should be able to extend subseq to work for any new collection by customizing those methods.

However, the current implementation of subseq assumes that the values you are sorting on are unique, which is a reasonable assumption for the built-in sorted maps which sort on unique keys, but it is then impossible to extend subseq behavior to other types of collections. To give library designers the power to hook into subseq, this assumption needs to be removed.


1. A simple way is to allow for dropping multiple equal values when subseq massages the results of seqFrom into a strictly greater than sequence.

2. A better way is for subseq to delegate more of its logic to seqFrom (by adding an extra flag to the method call as to whether you
want greater than or equal or strictly greater than). This will allow for the best efficiency, and provide the greatest possibilities for future extensions.

Note: subseq currently returns () instead of nil in some situations. If the rest of this idea dies we might still want to fix that.

Patch clj-428-code-v5.patch implements approach #2 above. It preserves the current behavior of returning () instead of nil.

Patch: clj-428-code-v5.patch tests in clj-428-tests-v5.patch

Comment by Assembla Importer [ 24/Aug/10 10:10 AM ]

Converted from http://www.assembla.com/spaces/clojure/tickets/428

Comment by Andy Fingerhut [ 28/Apr/13 2:14 AM ]

Patch clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt dated Apr 28 2013 was written by Mark Engelberg in July 2010, and was attached to a message he sent to the dev thread linked in the description. The approach he takes is described by him in that thread, copied here:

Meanwhile, to initiate discussion on how to modify subseq, I've attached a proposed patch. This patch works by modifying the seqFrom method of the Sorted interface to take an additional "inclusive" parameter (i.e., <= and >= are inclusive, < and > are not).

In this patch, I do not address one issue I raised before, which is whether subseq implies by its name that it should return a seq rather than a sequence (in other words nil rather than ()). If seq behavior is desired, it would be necessary to wrap a call to seq around the calls to take-while. But for now, I'm just making the behavior match the current behavior.

Although I think this is the cleanest way to address the extensibility issue with subseq, the change to seqFrom will break anyone who currently is overriding that method. I didn't see any such classes in clojure.contrib, so I don't think it's an issue, but if this is a concern, my other idea is to fix the problem entirely within subseq by changing the calls to next into calls to drop-while. I have coded this to confirm that it works, and can provide that alternative patch if desired.

I can also supply a patch that uses drop-while in clojure.core/subseq and rsubseq if such an approach is preferred to the one in this patch.

Comment by Andy Fingerhut [ 28/Apr/13 12:12 PM ]

clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v2.txt dated Apr 28 2013 is same as clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt (soon to be deleted), except it adds tests for subseq and rsubseq, and corrects a bug in that patch. The approach is the same as described above for that patch.

Comment by Andy Fingerhut [ 01/May/13 2:44 AM ]

Patch clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt dated May 1 2013 is the same as clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt, still with the bug fix mentioned for -v2, but with some unnecessary changes removed from the patch. The comments for -v1.txt on the approach still apply.

Comment by Andy Fingerhut [ 14/Feb/14 12:20 PM ]

Patch clj-428-v4.diff is identical to clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt described in an earlier comment, except it updates some diff context lines so that it applies cleanly to the latest Clojure master as of today.

Comment by Andy Fingerhut [ 05/Jul/15 6:08 PM ]

Files clj-428-code-v5.patch and clj-428-tests-v5.patch are identical to the previous -v4 attachment, except they apply cleanly to the latest Clojure master. The code and tests are in separate files since they have different authors, and it will be easier to update such patches in the future if they are kept separate.

Generated at Sun Dec 04 02:21:40 CST 2016 using JIRA 4.4#649-r158309.