对 subseq 和 rsubseq 增强以支持优先映射了吗？

Question

在 http://groups.google.com/group/clojure-dev/browse_thread/thread/fdb000cae4f66a95 中查看开发线程。

摘自 Mark Engelberg 在 2010 年 7 月 14 日该讨论线程中的消息。

只有对核心进行补丁，才能正确实现 priority maps 上的 subseq。subseq 通过委派很多行为给 Java 方法 seqFrom、seq、entryKey 和 comparator 来实现其多态行为（在排序映射和排序集中）。因此，在理论上，您应该能够通过自定义这些方法来扩展 subseq 以适用于任何新的集合。

然而，subseq 当前的实现假设排序的值是唯一的，这对于在唯一键上进行排序的内置排序映射是一个合理的假设，但是将 subseq 的行为扩展到其他类型的集合是不可能的。为了给库设计者提供钩入 subseq 的能力，需要移除这个假设。

方法

1. 一种简单的方法是在 subseq 对 seqFrom 的结果进行杰出大于序列处理时允许删除多个相等的值。

2. 更好的方法是将更多逻辑委托给 seqFrom（通过添加一个额外的标志，在方法调用中指定是否要大于、大于等于或严格大于）。这将允许最高效，并为未来的扩展提供最大可能性。
   注意：在某种情况下，subseq 当前返回空列表 () 而不是 nil。如果这个想法实现不了，我们仍然可能希望修复这个问题。

补丁 clj-428-code-v5.patch 实现上述第 2 个方法。它保留了返回 () 而不是 nil 的当前行为。

补丁：clj-428-code-v5.patch 测试在 clj-428-tests-v5.patch 中。

补丁：clj-428-code-v5.patch 测试在 clj-428-tests-v5.patch 中

Answer 1

评论者：导入器

从 http://www.assembla.com/spaces/clojure/tickets/428 转换而来

Answer 2

评论者：jafingerhut

日期为2013年4月28日的补丁文件clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt由Mark Engelberg于2010年7月编写，并附加在描述中提供的dev线程的邮件中。他在该线程中描述了他的方法，此处复制

---

同时，为了发起关于如何修改subseq的讨论，我附上了一个提出的补丁。此补丁通过修改Sorted接口的seqFrom方法，增加一个额外的“inclusive”参数（即<=和>=是包含的，<和>是不包含的）来实现。

在这个补丁中，我没有解决我之前提出的一个问题，即subseq的名称是否意味着它应该返回一个序列而不是一个序列（换句话说nil而不是()）。如果需要seq行为，可以在调用take-while之前将其调用包装起来。但到目前为止，我只是使行为与当前行为匹配。

尽管我认为这是解决subseq的可扩展性问题最干净的方法，但对seqFrom的更改将会破坏目前正在重写该方法的任何人。在clojure.contrib中没有看到这样的类，所以我认为这不是一个问题，但如果这是一个担忧，我还有其他想法，即在subseq内部通过将调用next改为调用drop-while来完全解决这个问题。我已经对该解决方案进行了编码以确认其工作，如果需要可以提供该替代补丁。

我还可以提供一个补丁，该补丁使用clojure.core/subseq和rsubseq中的drop-while，如果这种方法比此补丁中的方法更受欢迎。

Answer 3

评论者：jafingerhut

日期为2013年4月28日的clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v2.txt与clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt相同（即将被删除），但增加了对subseq和rsubseq的测试，并修正了该补丁中的一个错误。该补丁的方法与上述补丁中描述的方法相同。

Answer 4

评论者：jafingerhut

日期为2013年5月1日的补丁文件clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt与clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt相同，仍然包含了之前对-v2提出的错误修复，但去除了补丁中的一些不必要更改。关于-v1.txt的评论仍然适用于该方法。

Answer 5

评论者：jafingerhut

补丁文件 clj-428-v4.diff 与之前评论中提到的 clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt 完全相同，但更新了一些diff上下文行，以便它能够干净地应用在今天最新的Clojure master版本上。

Answer 6

评论者：jafingerhut

文件 clj-428-code-v5.patch 和 clj-428-tests-v5.patch 与之前的-v4 附件相同，但它们可以干净地应用在最新的Clojure master上。由于代码和测试有不同的作者，因此它们分别在单独的文件中，以便将来更容易更新这类补丁。

Answer 7

评论者：marco.m

你好，有什么新消息吗？

Answer 8

评论者：alexmiller

根据目前的实现，这个变更将对Sorted造成破坏性改变，因此我认为仅在这一点上，该特定的补丁是不适合的。

但可能还是应该从宏观的角度来考虑。与其推动subseq及其含义，不如考虑一些抽象接口，它能够捕获Sorted之外的一些有趣的功能。我认为在这方面所付出的任何思考都是值得的。特别是，很有必要有一个想法，看看哪些现有的集合可能会从这方面受益。如果我们找不到2-3个，那么我认为我会把这个问题纳入待办事项，直到有一个有说服力的案例。特别是，这看起来与Java中的SortedSet -> NavigableSet之间有一些对应关系，也许需要类似的东西。

Answer 9

评论者：marco.m

感谢Alex，非常感谢您的回复以及您为之付出的思考 :-)

Answer 10

评论者：markengelberg

在我看来，衡量一种语言的重要手段是其内部抽象的程度，这些抽象用于其自身的数据结构，并且这些抽象是否对外开放以供扩展。正因如此，我一直认为这是一个值得解决的问题。在subseq和rsubseq中嵌入的假设，即有序集合只能具有唯一的有序值，无疑是初始代码中的一个疏忽，这个疏忽不仅阻止了优先映射（priority-map）钩入subseq和rsubseq，还阻止了Marczyk的几个巧妙的数据结构。我认为，除了Sorted中已有的内容外，并没有什么有趣的内容需要我们去理解——问题在于，按照subseq和rsubseq目前定义的样子，实现Sorted的seqFrom接口目前不足以满足它们的指定行为。你可以将这视为Sorted或subseq/rsubseq的不足。

Marco，clojure.data.priority-map的最新版本包含了对子序列subseq和逆序列rsubseq的补丁版本，它不依赖于底层Sorted接口的更改，以修复其在对具有重复有序值的有序集合上的错误行为。您可以自由使用该实现与优先映射（priority-map）或您可能正在构建的任何其他类似数据结构。

我不能代表Clojure团队，但我会认为，如果有人主动对clojure.data.priority-map中的subseq和rsubseq进行广泛的基准测试，并确定它们对现有的有序Clojure数据结构没有性能影响，那么他们可能会更愿意将修补后的版本移至Clojure的核心库中，因为这将带来明确的好处而没有任何劣势。（或者，如果现有有序数据结构存在性能影响，找出如何调整以避免性能损失，这应该很容易做到）。对subseq和rsubseq所需的更改很简单：现在它们通过调用rest来将<=子序列转换为<子序列，从而删除第一个项目，我仅仅是将它们更改为调用drop-while来删除序列前面的所有相等项，因为这些可能不止一个。当这个问题首次提出时，核心团队成员表示他们更愿意在协议层面解决这个问题，但如果这不再可行，我希望考虑这一修改对subseq和rsubseq的影响。这似乎是一个简单的解决长期存在的问题的方法，该问题阻碍了subseq和rsubseq与所有满足Sorted的seqFrom实现的数据结构一起工作。

Answer 11

评论者：alexmiller

我只是想提一下，这是我第一次记得查看这个工单，因为它基本上在我的Clojure核心参与之前。我知道已经过去很多年了，我实际上在尝试诚实地思考这个问题。但我可能在你走过的每一步都会问一些愚蠢的问题。

我确实同意让良好的集合特性能够在Clojure核心内部和外部被实现所使用。

关于更改协议的可行性，我认为可能你在那里误解了我的意图。我们当然可以更改或扩展协议，但我们只需要以扩展（保留现有内容）而不是中断（通过更改现有方法签名）的方式去做。我反对的是更改Sorted.seqFrom()的签名，这会破坏所有现有的实现 - 这绝对是不可能的。但是，将Sorted扩展到Sorted2（或任何更有意义的名称）并添加seqFrom的新算子是完全可以接受的。如果coll是Sorted2，子序列代码可以做到最好，如果不是，则回退到其他内容。有各种各样的方式来做这件事，但希望你能理解意图——现有的内容继续按原样工作，而新的内容如果可用则可以被利用。

回顾起来，似乎seqFrom及其相关功能没有足够丰富，无法涵盖不同数据结构中可能需要的所有内容。我继续认为NavigableSet有很多好的前期思考（并不是说它是直接的答案，但它实际上是同一个问题领域），并且更广泛地研究近年来加入的一些其他数据结构，看看我们能实现什么是有益的。

事实上，子序列的全套实现相当粗糙，依赖于许多移动部件和假设。也许该给集合做一个直接实现的任务。

Answer 12

评论者：markengelberg

问题的关键在于，subseq允许使用<=，<，>=，>，而seqFrom只能使用<=，>=，然后subseq“按摩”seqFrom的输出以转换为<，>，如果有多于一个相等的项则不起作用。我认为这是一个设计缺陷的原因是，您可以创建一个seqFrom的实现，它可以准确地完成实现所需的所有操作（生成适当的<=和>=子序列），但subseq和rsubseq可能仍然不正确。

很久以前，想法似乎是，“嘿，seqFrom和subseq/rsubseq之间的不匹配相当糟糕。让我们让集合在自己的seqFrom实现中完成所有subseq/rsubseq逻辑，这样就不需要按摩两种可能的subseq为四种了。”

可以通过更改subseq和rsubseq以丢弃所需的任何项来修复它们，而不需要更改接口，但如果集合可以直接执行所有逻辑，那么集合可能比在subseq和rsubseq级别进行修复更有效地创建<，>子序列。

我理解你的Sorted2接口观点。

Answer 13

评论者：alexmiller

我认为这是一句有帮助的关于问题的重述。我觉得“修复”subseq的drop逻辑只是进一步覆盖这种脱节，这在帮助用户时可能更有帮助（并且更有效）允许集合直接完成用户需要的操作。

Answer 14

评论者：alexmiller

例如，你可以有一个Subseqable接口，如果subseq/rsubseq检测到它，它们就直接将控制权传递给集合。

Answer 15

参考：https://clojure.atlassian.net/browse/CLJ-428 (由stu报告)