2024 年 Clojure 状态调查!中分享您的想法。

欢迎!请查阅关于页面了解此功能更多信息。

0
集合

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

以下为 Mark Engelberg 在 2010 年 7 月 14 日该讨论线程中的邮件摘录

要正确实现核心上的 subseq 对优先级映射的支持,仅通过修订是很可能的。subseq 通过委托大部分行为到 Java 方法 seqFrom、seq、entryKey 和 comparator 来实现其多态行为(在有序映射和有序集合中)。所以理论上,您应该能够通过自定义这些方法来扩展 subseq 以适用于任何新的集合。

然而,subseq 的当前实现假定排序所依据的值是唯一的,这对于内置的有序映射来说是一个合理的假设,因为它们按唯一键排序,但然后将 subseq 行为扩展到其他类型的集合是不可能的。为了给库设计者提供 hook 到 subseq 的能力,这个假设需要被取消。

方法

  1. 一种简单的方法是在 subseq 将 seqFrom 的结果处理为一个严格大于序列时,允许丢弃多个相同的值。

  2. 更好的方法是让 subseq 将更多逻辑委托给 seqFrom(通过在方法调用中增加一个额外的标志来表示你
    想要的是大于、大于等于还是严格大于)。这将允许获得最佳的效率,并为未来的扩展提供最大的可能性。

注意:subseq 在某些情况下目前返回空列表而不是nil。如果这个想法失败,我们可能仍然想要修复这个问题。

Patch clj-428-code-v5.patch 实现了上述方法 #2。它保留了在返回空列表而不是nil的当前行为。

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

15 个答案

0

评论由:importer 提出

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

0

评论者:jafingerhut

2013年4月28日的补丁文件clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v1.txt由Mark Engelberg于2010年7月编写,并将其附加在描述中链接的开发线程发送的消息中。他在该线程中描述了其采用的方案,此处复制。


同时,为了就如何修改subseq进行讨论,我已附加了一个提议的补丁。这个补丁通过修改Sorted接口的seqFrom方法来接受一个额外的“inclusive”(包含)参数(即< <= > 和 >= 是包含的,< 和 > 不是)。

在这段补丁中,我没有解决我之前提出的一个问题,即subseq的名字是否暗示它应该返回一个序列(即nil而不是()`)。如果需要seq行为,就需要围绕take-while调用包装一个对seq的调用。但到目前为止,我只是让行为与当前行为相匹配。

虽然我认为这是解决subseq扩展性问题最干净的方法,但这种对seqFrom的改变将破坏当前正在重写该方法的人。我没有在clojure.contrib中看到这样的类,所以我认为这不是问题,但如果这有问题,我的另一个想法是在subseq内完全解决问题,通过将调用next更改调用drop-while。我已经编写了代码来确认它是可行的,如果需要,我可以提供这个替代补丁。

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

0

评论者: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添加了测试,并纠正了该补丁中的错误。该方法与上述补丁描述的相同。

0

评论者: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相同,仍然有提到的-bug修复,但删除了一些不必要的更改。关于-v1.txt的评论仍适用于该方法的描述。

0

评论者:jafingerhut

补丁文件clj-428-v4.diff与早期评论中描述的clj-428-change-Sorted-seqFrom-to-take-inclusive-patch-v3.txt相同,除了它更新了一些diff上下文行,以便在今天对最新的Clojure master版本进行干净应用。

0

评论者:jafingerhut

文件clj-428-code-v5.patch和clj-428-tests-v5.patch与之前的-v4附件相同,但它们可以干净地应用于最新的Clojure主分支。由于代码和测试是由不同作者编写的,因此将它们保存在单独的文件中会使未来的补丁更新更容易。

0

评论区由:marco.m 发表

你好,有什么最新消息吗?

0

评论区由:alexmiller 发表

按照实现方式,这个变更将会对Sorted造成破坏性变更,所以仅仅基于这一点,我认为那个特定的补丁在Sorted上是不适用的。

但也许应该关注更高层面。与其推动subseq及其意义,不如考虑一个能够捕捉到比Sorted中更有趣的东西的抽象接口。对于那个想法,我认为是值得投入思考的。特别是,的好奇心在于2或3个现有的可能从这中受益的集合。如果我们找不到2或3个这样的集合,我认为我会将它存档直到出现有说服力的案例。特别是,这似乎与SortedSet -> NavigableSet在Java中的对应是一致的。

0

评论区由:marco.m 发表

谢谢Alex,真的非常感激你的回复和你付出的思考 :-)

0

评论区由:markengelberg 发表

我认为衡量一种语言的一个重要指标是其内部抽象的可扩展性,这些抽象用于其自身的数据结构。因此,我一直认为这是一个值得解决的问题。subseq和rsubseq在初始代码中对排序集合只能拥有唯一排序值的假设,显然是一个疏忽,不仅阻碍了优先映射挂钩subseq和rsubseq,还阻碍了Marczyk的几个巧妙的数据结构。我不认为Sorted之外还有什么有趣的内容需要我们尝试理解——问题是,目前sorted的seqFrom接口实现对于subseq和rsubseq来说不足以提供他们指定的行为。您可以将这视为Sorted的缺陷或subseq/rsubseq的缺陷。

Marco,clojure.data.priority-map的最新版本包含了一个修补版的subseq和rsubseq,它不依赖于对底层Sorted接口的改变,以修复其在排序集合(具有重复排序值)上的不正确行为。您可以随意使用该实现与priority-map或您可能构建的任何其他相似的数据结构。

我无法代表Clojure团队发表意见,但我想,如果有人主动对clojure.data.priority-map中的subseq和rsubseq进行广泛的基准测试,并证实不会对现有排序Clojure数据结构造成性能损失,那么他们可能会倾向于将这些修补版本移入Clojure的核心,因为这会带来明显的好处而没有负面影响。(或者如果与Clojure的现有排序数据结构相比有性能损失,想办法调整以消除性能损失,这应该很容易做到)。对subseq和rsubseq所需的变化很简单:它们目前通过调用rest丢弃第一个元素将≤子序列转换为<子序列,我只是将它们改为调用drop-while来丢弃序列前面的所有相等项,因为可能不止一个。当这个问题最初提出时,核心团队成员表示他们更希望看到在协议级别解决这个问题,但如果这不再可行,我建议考虑对subseq和rsubseq进行此更改。这似乎是一个简单的方法来修复这个长期存在的问题,防止subseq和rsubseq与所有实现Sorted seqFrom接口的数据结构一起工作。

0
回答者:

评论区由:alexmiller 发表

我只是想指出,这是我第一次记住查看这个票据,因为它基本上早于我在Clojure核心中的参与。我知道这一切已经过去多年了,我正在努力真诚地思考这个问题。但在我重新走过的路上,我可能会提出一些愚蠢的问题。

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

关于更改协议的可行性,我认为您可能误解了我的意图。我们当然可以更改或扩展协议,但我们只需要以一种渐进(保留现有内容)而不是破坏(通过更改现有方法签名)的方式进行。我的反对意见是更改Sorted.seqFrom()的签名,因为这会破坏所有现有实现——这根本不可行。但将Sorted扩展到Sorted2(或任何更有意义的名字)并添加新的seqFrom参数是完全可行的。子序列代码可以在集合是Sorted2的情况下执行最佳操作,如果只是Sorted,则回退到其他选项。有多种方法可以实现这一点,但希望您理解意图——现有内容继续按原样工作,如果可用,则利用新功能。

退回到一开始,seqFrom和其他功能似乎不足以覆盖不同数据结构可能需要的所有内容。我仍然认为NavigableSet有很多好的先验思想(并不是说它是直接答案,但它确实是同一个问题领域),并且研究一下近年来添加的其他数据结构可能会让我们有所作为。

实际上,子序列功能的实现相当粗糙,依赖于很多移动部件和假设。也许应该将整个子序列操作直接交给集合来执行。

0

评论区由:markengelberg 发表

问题的核心在于子序列允许 <=, <, >=, >,而seqFrom只允许 <=, >=,然后子序列将seqFrom的输出进行“按摩”,以转换为 <, >,这会丢弃多达一项,如果有多个相等的项,则不起作用。我认为这是一个设计缺陷,因为您可以为seqFrom实现创建一个实现,该实现完全满足要求(生成适当的 <= 和 >= 子序列),但子序列和反子序列可能仍然不正确。

很早以前的想法似乎是这样的,“嘿,seqFrom和子序列/反子序列之间的这种不匹配有点糟糕。让我们让集合在其seqFrom的实现中进行所有子序列/反子序列逻辑,这样就不需要将两个可能的子序列按摩成四种可能的子序列。”

可以通过固定子序列和反子序列来丢弃必要数量的项,而无需更改接口,但如果集合可以直接执行所有逻辑,它可能在子序列和反子序列级别进行修复的情况下,更有效地创建 <, > 子序列。

我明白你的观点,关于Sorted2接口。

0

评论区由:alexmiller 发表

我认为这是一种有帮助的问题重述。我觉得“修正”子序列的丢弃逻辑只是掩盖了这个断开连接的问题,而当更有帮助(更有效)的时候,允许集合直接执行用户需要的操作。

0
by

评论区由:alexmiller 发表

例如,您可以为Subseqable接口提供支持,如果subseq/rsubseq检测到它,它们只需将控制权传递给集合。

0
by
...