将F#中的平面序列懒散地分组 [英] Lazily grouping a flat sequence in F#

问题描述

给出以下一系列项目:

[ ("a", 1); ("a", 2); ("a", 3); ("b", 1); ("c", 2); ("c", 3) ]

如何将其懒惰地转换为:

How can I convert this lazily into:

{ ("a", { 1; 2; 3}); ("b", { 1 }); ("c", { 2; 3}) }

您可以假设输入数据源已经在分组键元素上进行了排序，例如"a"，"b"和"c".

You can assume that the input data source is already sorted on the grouping key element e.g. "a" "b" and "c".

我在这里使用{}表示这是一个延迟评估的项目序列.

I'm using the { } there to indicate that it's a lazily-evaluated sequence of items.

我已经使它必须通过两个在源序列的IEnumerator上运行的while循环来工作，但这涉及到创建参考变量和突变等.我敢肯定，有更好的方法可以做到这一点，也许递归或使用Seq库中的某些操作，例如扫描还是展开?

I've gotten it working imperatively with two while loops operating over the IEnumerator of the source sequence, but this involves creating reference variables and mutation etc. etc. I'm sure that there are better ways of doing this, perhaps with Recursion or using some of the operations in the Seq library e.g. scan or unfold?

推荐答案

如果您想在IEnumerable<'T>上实现它(使其变得懒惰)，那么它必然会变得势在必行，因为IEnumerator<'T>类型用于迭代输入的命令势在必行.但是其余的可以使用序列表达式编写为递归函数.

If you want to implement this over IEnumerable<'T> (to make it lazy), then it is necessarily going to be somewhat imperative, because the IEnumerator<'T> type that is used to iterate over the input is imperative. But the rest can be written as a recursive function using sequence expressions.

以下内容在第一层是懒惰的(它会懒惰地生成每个组)，但是不会懒惰地生成该组的元素(我认为这会具有相当微妙的语义):

The following is lazy in the first level (it produces each group lazily), but it does not produce elements of the group lazily (I think that would have pretty subtle semantics):

/// Group adjacent elements of 'input' according to the 
/// keys produced by the key selector function 'f'
let groupAdjacent f (input:seq<_>) = seq {
  use en = input.GetEnumerator()

  // Iterate over elements and keep the key of the current group
  // together with all the elements belonging to the group so far
  let rec loop key acc = seq { 
    if en.MoveNext() then 
      let nkey = f en.Current 
      if nkey = key then 
        // If the key matches, append to the group so far
        yield! loop key (en.Current::acc)
      else 
        // Otherwise, produce the group collected so far & start a new one
        yield List.rev acc
        yield! loop nkey [en.Current]
    else
      // At the end of the sequence, produce the last group
      yield List.rev acc
  }
  // Start with the first key & first value as the accumulator
  if en.MoveNext() then 
    yield! loop (f en.Current) [en.Current] }

不幸的是，此(非常有用！)函数未包含在标准F#库中，因此，如果要对 adjacent 元素(而不是使用Seq.groupBy的列表中的任意元素)进行分组，您必须自己定义...

Unfortunately, this (pretty useful!) function is not included in the standard F# library, so if you want to group adjacent elements (rather than arbitrary elements in the list using Seq.groupBy), you have to define it yourself...

这篇关于将F#中的平面序列懒散地分组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！