Clojure

subseq, rsubseq enhancements to support priority maps?

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: Backlog
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test

Description

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.

Approaches:

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

  1. clj-428-tests-v5.patch
    05/Jul/15 6:08 PM
    1 kB
    Andy Fingerhut
  2. clj-428-code-v5.patch
    05/Jul/15 6:08 PM
    4 kB
    Andy Fingerhut

Activity

Hide
Assembla Importer added a comment -
Show
Assembla Importer added a comment - Converted from http://www.assembla.com/spaces/clojure/tickets/428
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.

People

Vote (2)
Watch (3)

Dates

  • Created:
    Updated: