F#如何将一个序列按每n个元素拆分成子列表

Question

假设我有一个包含100个元素的序列。每10个元素，我希望得到前面10个元素的新列表。这样一来，我最终会得到一个包含10个子列表的列表。

Seq.take(10) 看起来很有希望，但如何重复调用它来返回一个列表的列表呢？

- yanta

Answer 1

现在有 Seq.chunkBySize 可用：

[1;2;3;4;5] |> Seq.chunkBySize 2 = seq [[|1; 2|]; [|3; 4|]; [|5|]]

- anvish

Answer 2

这不错：

let splitEach n s =
    seq {
        let r = ResizeArray<_>()
        for x in s do
            r.Add(x)
            if r.Count = n then
                yield r.ToArray()
                r.Clear()
        if r.Count <> 0 then
            yield r.ToArray()
    }

let s = splitEach 5 [1..17]
for a in s do
    printfn "%A" a
(*
[|1; 2; 3; 4; 5|]
[|6; 7; 8; 9; 10|]
[|11; 12; 13; 14; 15|]
[|16; 17|]
*)

- Brian

---

作为一项小的优化，您可以将 n 传递到 ResizeArray 构造函数中，以将初始容量设置为您知道它需要容纳的大小。 - Joel Mueller

我选择这个答案，因为它对我来说最容易理解。 - yanta

Answer 3

我有三种解决方案。没有一种保留输入元素的顺序，但这应该没问题。

我的第一个解决方案非常丑陋（利用ref单元格）：

//[[4; 3; 2; 1; 0]; [9; 8; 7; 6; 5]; [14; 13; 12; 11; 10]; [17; 16; 15]]
let solution1 =
    let split s n =
        let i = ref 0
        let lst = ref []
        seq {
            for item in s do
                if !i = n then
                    yield !lst
                    lst := [item]
                    i := 1
                else
                    lst := item::(!lst)
                    i := !i+1
            yield !lst
        } |> Seq.toList
    split {0..17} 5

我的第二种解决方案消除了第一种解决方案中对参考单元格的使用，但相应地强制使用直接的IEnumerator访问（从一侧推入，从另一侧弹出）！

//[[17; 16; 15]; [14; 13; 12; 11; 10]; [9; 8; 7; 6; 5]; [4; 3; 2; 1; 0]]
let solution2 =
    let split (s:seq<_>) n =
        let e = s.GetEnumerator()
        let rec each lstlst lst i =
            if e.MoveNext() |> not then
                lst::lstlst
            elif i = n then
                each (lst::lstlst) [e.Current] 1
            else 
                each lstlst ((e.Current)::lst) (i+1)
        each [] [] 0
    split {0..17} 5

我的第三个解决方案基于第二个解决方案，但是它“作弊”了，它使用列表作为输入而不是序列，这使得最优雅的解决方案成为可能，正如Tomas所指出的那样，这在序列中缺乏模式匹配（这就是我们被迫使用直接IEnumerator访问的原因）。

//[[17; 16; 15]; [14; 13; 12; 11; 10]; [9; 8; 7; 6; 5]; [4; 3; 2; 1; 0]]
let solution3 =
    let split inputList n =
        let rec each inputList lstlst lst i =
            match inputList with
            | [] -> (lst::lstlst)
            | cur::inputList ->
                if i = n then
                    each inputList (lst::lstlst) [cur] 1    
                else
                    each inputList lstlst (cur::lst) (i+1)
        each inputList [] [] 0
    split [0..17] 5

如果保留元素的顺序很重要，您可以使用 List.rev 来实现。例如，在 solution2 中，将 split 函数的最后一行改为以下内容：

each [] [] 0 |> List.rev |> List.map List.rev

- Stephen Swensen

Answer 4

也许这个简单的纯实现会有用：

let splitAt n xs =  (Seq.truncate n xs, if Seq.length xs < n then Seq.empty else Seq.skip n xs)

let rec chunk n xs =
    if Seq.isEmpty xs then Seq.empty
    else
        let (ys,zs) = splitAt n xs
        Seq.append (Seq.singleton ys) (chunk n zs)

例如：

> chunk 10 [1..100];;
val it : seq<seq<int>> =
  seq
    [seq [1; 2; 3; 4; ...]; seq [11; 12; 13; 14; ...]; 
     seq [21; 22; 23; 24; ...]; seq [31; 32; 33; 34; ...]; ...]

> chunk 5 [1..12];;
val it : seq<seq<int>> =
  seq [seq [1; 2; 3; 4; ...]; seq [6; 7; 8; 9; ...]; seq [11; 12]]

- vis

Answer 5

就我个人而言，我的想法是：

let rec split size list =
if List.length list < size then
    [list]
else
    (list |> Seq.take size |> Seq.toList) :: (list |> Seq.skip size |> Seq.toList |> split size)

- Édgar Sánchez Gordón

---

这种方法可能存在的问题是，每个块都会从开头开始枚举序列（直到块的末尾），因此迭代次数比所需迭代次数多约N/2倍（对于长度为N的序列）。 - Tomas Petricek

在调用此函数之前，您必须先将序列转换为列表吗？ - yanta

Answer 6

如果不确定，请使用折叠。

let split n  = let one, append, empty = Seq.singleton, Seq.append, Seq.empty
               Seq.fold (fun (m, cur, acc) x -> 
                           if m = n then (1, one x, append acc (one cur))
                           else (m+1, append cur (one x), acc))
                        (0, empty, empty)
               >> fun (_, cur, acc) -> append acc (one cur)

这种方法具有完全的功能，但每个输入序列元素只被触碰一次(*)（与上面提出的Seq.take+Seq.skip解决方案相反）。

（*）假设O(1) Seq.append。我当然希望如此。

- Søren Debois

Answer 7

我发现这是最快的：

let windowChunk n xs =
    let range = [0 .. Seq.length xs]
    Seq.windowed n xs |> Seq.zip range 
                      |> Seq.filter (fun d -> (fst d) % n = 0)
                      |> Seq.map(fun x -> (snd x))

即窗口列表，与整数列表压缩，删除所有重叠的元素，然后删除元组的整数部分。

- Rick Bradford

Answer 8

我认为Brian的解决方案可能是最合理的简单选项。序列的问题在于它们不能像函数列表一样轻松地使用通常的模式匹配。避免这种情况的一种选择是使用F# PowerPack中的LazyList。

另一个选项是为使用IEnumerator类型编写计算生成器。我最近写了类似的东西- 您可以在此处获取它。然后，您可以编写类似以下内容的代码：

let splitEach chunkSize (s:seq<_>) =
  Enumerator.toSeq (fun () -> 
    let en = s.GetEnumerator()
    let rec loop n acc = iter {
      let! item = en
      match item with 
      | Some(item) when n = 1 -> 
          yield item::acc |> List.rev 
          yield! loop chunkSize []
      | Some(item) -> 
          yield! loop (n - 1) (item::acc)
      | None -> yield acc |> List.rev }
    loop chunkSize [] )

这使得可以使用一些函数式模式进行列表处理 - 最值得注意的是，您可以将其编写为通常的递归函数（类似于您为列表/惰性列表编写的函数），但在内部它是命令式的（iter 的 let! 构造器获取下一个元素并修改枚举器）。

- Tomas Petricek