为什么clojure集合不直接实现ISeq接口？

Question

据说clojure中的每个集合都是"sequable",但只有list和cons实际上是seqs:

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

所有其他seq函数首先将集合转换为序列,然后才对其进行操作.

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接口和所有序列函数不返回相同的类的对象作为输入对象？

Answer 1

这已在Clojure谷歌小组讨论过; 例如,参见今年2月的线程图语义.我将冒昧地将我在消息中提出的一些要点重新用于下面的那个帖子,同时添加几个新的.

在我继续解释为什么我认为"单独的seq"设计是正确的之前,我想指出一个自然的解决方案,你真的希望输出类似于输入而不是明确的关于它fmap以contrib库algo.generic的函数形式存在.(我认为默认使用它并不是一个好主意,但是,核心库设计是一个很好的原因.)

概观

关键的观察,我认为,这是顺序操作,比如map,filter等概念上划分为三个独立的担忧:

1. 某种迭代输入的方式;

2. 将函数应用于输入的每个元素;

3. 产生一个输出.

显然2.如果我们能够处理1.和3,那就没有问题.所以让我们来看看那些.

迭代

对于1.,请考虑迭代集合的最简单且最高效的方法通常不涉及分配与集合相同的抽象类型的中间结果.在一个向量上通过一个chunked seq映射一个函数可能比subvec在每个调用产生"视图向量"(使用)的seq上映射一个函数要高得多next; 然而,后者是我们可以next在Clojure风格的矢量上做得最好的(即使在存在RRB树的情况下,当我们需要适当的子向量/向量切片操作来实现一个有趣的算法时,这是很好的,但是如果我们使用它们来实现可怕的遍历next.

在Clojure中,专门的seq类型维护遍历状态和额外功能,例如(1)有序映射和集合的节点堆栈(除了更好的性能,这比使用dissoc/ disj!的遍历具有更好的大O复杂度),(2)当前索引+用于将叶子数组包装为用于向量的块的逻辑,(3)用于散列映射的遍历"延续".通过这样的对象遍历集合比任何遍历subvec/ dissoc/的尝试都快disj.

但是,假设我们愿意接受在向量上映射函数时的性能损失.好吧,我们现在尝试过滤:

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

这里有一个问题 - 从矢量中删除元素没有好办法.(同样,RRB树在理论上可能有所帮助,但实际上,所有RRB切片和连接都涉及为过滤操作生成"真实矢量",这绝对会破坏性能.)

这是一个类似的问题.考虑这个管道:

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

在这里,我们受益于懒惰(或者更确切地说,从早期停止过滤和映射的能力;这里有一个涉及减速器的点,见下文).显然take可以重新排序map,但不能重新排序filter.

关键是如果可以filter隐式转换为seq,那么它也可以map; 并且可以对其他序列函数进行类似的参数.一旦我们为所有 - 或几乎所有 - 进行了论证,很明显seq返回专门的seq对象也是有意义的.

顺便说一下,在集合上过滤或映射函数而不产生类似的集合是非常有用的.例如,我们通常只关心将转换管道产生的序列减少到某个值或者调用每个元素的副作用函数的结果.对于这些场景,通过维护输入类型并没有任何东西可以获得,并且在性能上会丢失很多.

产生输出

如上所述,我们并不总是希望生成与输入相同类型的输出.但是,当我们这样做时,通常最好的方法是将输入的seq倾注到空输出集合中.

事实上,绝对没有办法为地图和集合做得更好.基本原因是,对于大于1的基数集,没有办法预测函数在集合上的映射输出的基数,因为该函数可以"粘合在一起"(产生相同的输出)任意输入.

此外,对于有序映射和集合,无法保证输入集的比较器能够处理来自任意函数的输出.

因此,如果在很多情况下没有办法map比通过单独执行seq和into单独考虑更好,并且考虑到它们本身如何seq以及如何into制作有用的原语,Clojure可以选择公开有用的原语并让用户撰写他们.这让我们map和into生产从一集一集,而留下我们的自由,没有去到into的时候没有通过产生一组来获得值阶段(或其他集合类型,视情况而定).

并非所有都是seq; 或者,考虑减速器

使用reducers时,在映射,过滤等时使用集合类型本身的一些问题不适用.

reducers和seqs之间的关键区别在于,clojure.core.reducers/map和朋友生成的中间对象只生成"描述符"对象,这些对象维护有关在减速器实际减少的情况下需要执行哪些计算的信息.因此,可以合并计算的各个阶段.

这允许我们做类似的事情

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

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

当然我们仍然需要明确我们的意思(into #{}),但这只是说"减速器管道在这里结束;请以集合的形式产生结果".我们也可以要求一个不同的集合类型(可能是一个结果的向量;请注意,f集合上的映射可能会产生重复的结果,我们可能在某些情况下希望保留它们)或标量值((reduce + 0)).

摘要

主要观点如下:

1. 迭代集合的最快方法通常不涉及产生类似于输入的中间结果;

2. seq 使用最快的迭代方式;

3. 通过映射或过滤转换集合的最佳方法涉及使用seq-style操作,因为我们希望在累积输出时非常快速地迭代;

4. 因此seq成为一个伟大的原始;

5. map并且filter,在他们选择处理seqs时,根据场景,可以避免没有上升的性能惩罚,受益于懒惰等,但仍然可以用于产生收集结果into;

6. 因此他们也做了很好的原始人.

其中一些要点可能不适用于静态类型语言,但当然Clojure是动态的.另外,当我们想要一个匹配输入类型的返回时,我们只是被迫明确它,并且它本身可能被视为一件好事.

Answer 2

序列是逻辑列表抽象.它们提供对(稳定的)有序值序列的访问.它们实现为集合视图(具体接口与逻辑接口匹配的列表除外).序列(视图)是一个单独的数据结构,它引用集合以提供逻辑抽象.

序列函数(map,filter等)采用"seqable"事物(可以产生序列的东西),在其上调用seq以产生序列,然后对该序列进行操作,返回新序列.您是否需要或如何将该序列重新收集到具体集合中取决于您.虽然向量和列表是有序的,但是集合和映射不是,因此这些数据结构上的序列必须计算并保留集合外的顺序.

mapv,filterv,reduce-kv等专用函数允许您在知道希望操作在结尾而不是序列中返回集合时保持"在集合中".