为什么 F# 的 Seq.windowed 返回一个数组序列

Question

在F#中，Seq.windowed返回一个序列，其中每个窗口都是一个数组。为什么每个窗口都返回数组（一种非常具体的类型）而不是另一个序列或IList<'T>？例如，IList<'T>如果目的是表达窗口的项可以随机访问，则足够了，但是数组有两个含义：元素是可变和可随机访问的。如果您可以说明选择数组的理由，那么windowed与Seq.groupBy有何不同？为什么后者（或同类操作符）也不以数组的形式返回组的成员？

我想知道这是否只是设计上的疏忽还是数组背后有更深层次的契约原因？

- Atif Aziz

---

一个原因是，数组的速度明显更快。然而，如果你将它们与无限序列一起使用，你将不得不调整它们的大小，对于“windowed”，大小是已知的，所以为什么不在可以使用最快的集合类型时使用它呢？ - John Palmer

如果理由是效率，那么为什么不在 groupBy 中执行相同的操作，其中组的成员也可以作为数组返回？换句话说：Seq.groupBy: seq<'Key * seq<'T []>>。 - Atif Aziz

为什么在 seq<'t> 中要添加额外的 []？我怀疑你的意思是 'seq<'Key * 'T[]>`，但这会对无限序列造成失败，因为它需要无限大的数组，但你可以使用原始定义来处理无限序列。 - John Palmer

@JohnPalmer groupBy文档中指出“不应与大型或无限序列一起使用”，因为它“对原始序列的排序没有任何假设”。有序的groupBy或groupAdjacent的情况是不同的，因为它可以在不必完全遍历输入序列的情况下流式传输组。 - Atif Aziz

我从未考虑过IList或ICollection是不可变的，因为它有一个“Add”方法...仅在运行时不可变是不够的。 - Mauricio Scheffer

Answer 1

我不知道这背后的设计原则是什么。我猜可能只是实现中的一个偶然方面，因为Seq.windowed可以通过将项存储在数组中很容易地实现，而Seq.groupBy可能需要使用一些更复杂的结构。

总的来说，我认为F# API要么使用'T[]，如果使用数组是自然高效的实现方式，或者当数据源可能是无限的、惰性的或者实现必须显式将数据转换为数组时，返回seq<'T>（此时可以让调用者处理）。

对于Seq.windowed，我认为数组是一个很好的选择，因为你知道数组的长度，所以你很可能会使用索引。例如，假设prices是日期-价格元组的序列(seq<DateTime * float>)，你可以这样写:

prices
|> Seq.windowed 5
|> Seq.map (fun win -> fst (win.[2]), Seq.averageBy snd win)

这个示例计算浮动平均值，并使用索引获取中间的日期。

总之，我没有关于设计理念的很好解释，但我对所做选择感到非常满意 - 它们似乎在函数的通常用例中运行得非常好。

- Tomas Petricek

---

你能举出一些例子来说明“如果使用数组是自然高效的实现方式，F# API通常会使用'T[]'”吗？在Seq的情况下，只有toArray和windowed。 - Atif Aziz

Answer 2

几点思考：

首先，需要知道的是，在它们当前的版本中，Seq.windowed和Seq.groupBy都在它们的实现中使用非惰性集合。 windowed使用数组并返回数组。 groupBy建立了一个Dictionary<'tkey, ResizeArray<'tvalue>>，但将其保密，并将组值作为seq而不是ResizeArray返回。

从groupBy返回ResizeArray与其他任何内容都不符，因此显然需要隐藏它。另一种选择是返回数据的ToArray()。这将需要创建另一个数据副本，这是一个缺点。而且没有真正的好处，因为您事先不知道您的组会有多大，因此您不期望进行随机访问或数组启用的任何其他特殊操作。因此，简单地包装在seq中似乎是一个不错的选择。

对于windowed，情况就不同了。在这种情况下，您需要返回一个数组。 为什么？ 因为您已经知道该数组的大小，所以可以安全地进行随机访问或更好的模式匹配。 这是一个巨大的优势。 然而，缺点仍然存在-每个窗口都需要将数据重新复制到新分配的数组中。

seq{1 .. 100} |> Seq.windowed 3 |> Seq.map (fun [|x; _; y|] -> x + y)

仍然存在一个未解决的问题 - “我们不能通过仅内部使用真正的惰性序列并将它们作为这样返回来避免数组分配/复制的缺点吗？这不是更符合‘序列的精神’吗？” 这可能有点棘手（可能需要一些高级的枚举克隆？），但是可以肯定，通过一些小心编码，应该是可以实现的。 但是这样做有一个巨大的缺点。 你需要在内存中缓存整个未展开的序列才能使其工作，这有点否定了懒惰执行的整个目标。与列表或数组不同，多次枚举序列不能保证产生相同的结果（例如返回随机数的序列），因此这些返回的序列窗口的后备数据需要被缓存在某个地方。当最终访问该窗口时，你不能只是插入并重新枚举原始源序列 - 你可能会得到不同的数据，或者序列可能在不同的位置结束。这指向了在Seq.windowed中使用数组的另一个优点 - 只需要一次在内存中保留windowSize个元素。

- latkin

Answer 3

这当然只是猜测。我认为这与两个函数的实现方式有关。如前所述，在Seq.groupBy中，组的长度是可变的，在Seq.windowed中，它们是固定大小的。因此，在Seq.windowed的实现中，使用固定大小的数组比在Seq.groupBy中使用Generic.List（在F#中称为ResizeArray）更有意义。现在，尽管可变的，但是Array在F#代码和库中被广泛使用，并且F#提供了语法支持来创建、初始化和操作数组，而ResizeArray在F#代码中并没有得到广泛使用，除了类型别名之外，语言没有提供任何语法支持，所以我认为这就是他们决定将其公开为Seq的原因。

- Gus