clojure - 为什么Clojure集合不直接实现ISeq接口(interface)？

Question

据说clojure中的每个集合都是“顺序的”，但是只有list和cons实际上是seqs：

user> (seq? {:a 1 :b 2})
false
user> (seq? [1 2 3])
false    

所有其他 seq functions首先将集合转换为序列，然后对其进行操作。

user> (class (rest {:a 1 :b 2}))
clojure.lang.PersistentArrayMap$Seq

我不能做这样的事情：

user> (:b (rest {:a 1 :b 2}))
nil
user> (:b (filter #(-> % val (= 1)) {:a 1 :b 1 :c 2}))
nil

并且必须强制回到具体的数据类型。对我来说，这看起来像是糟糕的设计，但很可能我还没有明白。

那么，为什么clojure集合不直接实现ISeq接口，并且所有seq函数都没有返回与输入对象相同类的对象？

Answer 1

Clojure google小组对此进行了讨论；例如，请参见今年2月的线程map semantics。我会随意使用我在消息中对下面的线程提出的观点，同时添加一些新观点。

在继续解释为什么我认为“ sequate seq”设计是正确的设计之前，我想指出一个自然的解决方案，用于您确实希望输出与输入类似但又不明确的情况关于它的信息以contrib库algo.generic中的函数fmap的形式存在。 （但是，出于默认原因，核心库设计是一个好的原因，我认为默认情况下使用它不是一个好主意。）

总览

我认为，关键的观察结果是诸如map，filter等序列操作在概念上分为三个独立的方面：


对他们的输入进行某种迭代的方式；
将函数应用于输入的每个元素；
产生输出。


显然，如果我们能够处理1.和3，则2.毫无问题。所以让我们来看一下。

迭代

对于1.，请考虑最简单，最高效的迭代集合的方法通常不涉及分配与集合相同的抽象类型的中间结果。将函数映射到向量上的分块seq上比将函数映射到产生对每个subvec的“视图向量”（使用next）（使用next）的seq上的性能要好得多。但是，后者是我们可以在Clojure风格的向量上对next进行性能优化的最佳方法（即使存在RRB trees，当我们需要适当的子向量/向量切片操作来实现有趣的效果时，这也很棒）算法，但是如果我们使用遍历实现dissoc，则遍历的速度会很慢。

在Clojure中，专门的seq类型维护遍历状态和额外的功能，例如（1）用于排序映射和集合的节点堆栈（除了更好的性能之外，与使用disj / subvec遍历相比，它具有更大的big-O复杂性！） ，（2）当前索引+逻辑，用于将叶子数组包装在矢量块中；（3）遍历“连续”用于哈希图。通过这样的对象遍历集合比通过dissoc / disj / take遍历任何尝试都快。

但是，假设在将函数映射到向量时我们愿意接受性能下降。好吧，让我们现在尝试过滤：

(->> some-vector (map f) (filter p?))

这里有一个问题-没有从向量中删除元素的好方法。 （同样，RRB树在理论上可能会有所帮助，但实际上，所有涉及为过滤操作生成“实际矢量”的RRB切片和级联都将绝对破坏性能。）

这是一个类似的问题。考虑以下管道：

(->> some-sorted-set (filter p?) (map f) (take n))

这里我们从懒惰中受益（或者更确切地说，从早期停止过滤和映射的能力中受益；这里有一个涉及reduces的要点，请参见下文）。显然 map可以用 filter重新排序，但不能用 filter重新排序。

关键是，如果 map隐式转换为seq是可以的，那么 seq也可以。其他序列函数也可以使用类似的参数。一旦我们对所有（或几乎所有）参数都进行了说明，很明显 seq返回专门的 map对象也是有意义的。

顺便说一句，在集合上过滤或映射函数而不会产生类似的集合非常有用。例如，通常我们只关心将转换流水线产生的序列减少到某个值的结果，或者只关心在每个元素处产生副作用的函数。对于这些情况，通过保持输入类型无法获得任何好处，并且会损失很多性能。

产生输出

如上所述，我们并不总是希望产生与输入相同类型的输出。但是，当我们这样做时，通常最好的方法是进行将输入序列灌入空输出集合的等效操作。

实际上，绝对没有办法对地图和集合做得更好。根本原因是，对于基数大于1的集合，无法预测将函数映射到集合的输出的基数，因为函数可以“粘在一起”（为任意输入产生相同的输出）。

另外，对于排序的映射和集合，不能保证输入集合的比较器将能够处理任意函数的输出。

因此，如果在许多情况下，没有办法比单独进行 seq和 into并考虑 seq和 into自身如何制作有用的原语的方法要好得多，例如 map是的，Clojure可以选择公开有用的原语，然后让用户编写它们。这使我们 into和 into从一个集合中生成一个集合，同时又使我们可以自由地自由地进入当生成一个集合（或其他集合类型）无法获得任何价值的时候进入 clojure.core.reducers/map阶段。 ， 视情况可以是）。

并不是全部都是seq；或者，考虑减速器

在使用reducers时，在进行映射，过滤等操作时使用集合类型本身的某些问题不适用。

精简器和seqs之间的主要区别在于，由 (into #{})和朋友产生的中间对象仅生成“描述符”对象，该对象维护有关在精简精简器的情况下需要执行哪些计算的信息。因此，计算的各个阶段可以合并。

这使我们可以做类似的事情

(require '[clojure.core.reducers :as r])

(->> some-set (r/map f) (r/filter p?) (into #{}))

当然，我们仍然需要明确说明 f，但这只是说“ reducers管道在这里结束；请以集合的形式产生结果”的一种方式。我们还可以要求使用不同的集合类型（也许是结果的向量；请注意，将 (reduce + 0)映射到集合上可能会产生重复的结果，并且在某些情况下我们可能希望保留它们）或标量值（ seq） 。

摘要

要点如下：


迭代集合的最快方法通常不涉及产生类似于输入的中间结果；
seq使用最快的方法进行迭代；
通过映射或过滤来转换集合的最佳方法是使用 seq样式的操作，因为我们要在累积输出的同时非常快速地进行迭代；
因此 map是一个很好的原始语言；
根据情况， filter和 into在选择处理seq时，可以避免性能损失而没有上升空间，得益于懒惰等，但仍可以用于生成 的收集结果；
因此他们也创造了伟大的原始人。


其中有些观点可能不适用于静态类型的语言，但是Clojure当然是动态的。另外，当我们确实希望返回一个与输入类型匹配的返回值时，我们仅被迫明确要求它本身就可以被视为一件好事。