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-code-v5.patch
    05/Jul/15 6:08 PM
    4 kB
    Andy Fingerhut
  2. clj-428-tests-v5.patch
    05/Jul/15 6:08 PM
    1 kB
    Andy Fingerhut

Activity

Aaron Bedra made changes -
Field Original Value New Value
Fix Version/s Approved Backlog [ 10034 ]
Fix Version/s Release.Next [ 10038 ]
Reporter Assembla Importer [ importer ]
Affects Version/s Approved Backlog [ 10034 ]
Priority Blocker [ 1 ]
Aaron Bedra made changes -
Priority Blocker [ 1 ] Minor [ 4 ]
Andy Fingerhut made changes -
Attachment clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt [ 11970 ]
Andy Fingerhut made changes -
Patch Code [ 10001 ]
Andy Fingerhut made changes -
Attachment clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v2.txt [ 11973 ]
Andy Fingerhut made changes -
Attachment clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt [ 11970 ]
Andy Fingerhut made changes -
Attachment clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt [ 11977 ]
Andy Fingerhut made changes -
Attachment clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v2.txt [ 11973 ]
Alex Miller made changes -
Fix Version/s Approved Backlog [ 10034 ]
Fix Version/s Backlog [ 10035 ]
Alex Miller made changes -
Affects Version/s Approved Backlog [ 10034 ]
Affects Version/s Backlog [ 10035 ]
Alex Miller made changes -
Fix Version/s Backlog [ 10035 ]
Andy Fingerhut made changes -
Attachment clj-428-v4.diff [ 12793 ]
Andy Fingerhut made changes -
Attachment clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt [ 11977 ]
Andy Fingerhut made changes -
Patch Code [ 10001 ] Code and Test [ 10002 ]
Andy Fingerhut made changes -
Reporter Assembla Importer [ importer ] Stuart Halloway [ stu ]
Andy Fingerhut made changes -
Description See dev thread at http://groups.google.com/group/clojure-dev/browse_thread/thread/fdb000cae4f66a95.

Note: subseq currently returns () instead of nil in some situations. If the rest of this idea dies we might still want to fix that.
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.

I proposed two possible ways to patch subseq:

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

2. The 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.
Andy Fingerhut made changes -
Attachment clj-428-tests-v5.patch [ 14306 ]
Attachment clj-428-code-v5.patch [ 14305 ]
Andy Fingerhut made changes -
Attachment clj-428-v4.diff [ 12793 ]
Andy Fingerhut made changes -
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.

I proposed two possible ways to patch subseq:

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

2. The 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.
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.

*Patch*: clj-428-code-v5.patch tests in clj-428-tests-v5.patch
Andy Fingerhut made changes -
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.

*Patch*: clj-428-code-v5.patch tests in clj-428-tests-v5.patch
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

People

Vote (2)
Watch (3)

Dates

  • Created:
    Updated: