在 F# 中编写 batchesOf size seq 的最惯用方法

Question

我正在尝试通过将一些 C# 算法重写为惯用的 F# 来学习 F#。

我尝试重写的第一个函数是batchesOf，其中：

[1..17] |> batchesOf 5

它将序列分成批次，每个批次最多有五个，即：

[[1; 2; 3; 4; 5]; [6; 7; 8; 9; 10]; [11; 12; 13; 14; 15]; [16; 17]]

我第一次尝试这样做有点丑陋，我不得不使用尝试在闭包内使用 mutable 类型时遇到错误后的可变 ref 对象。使用 ref 特别令人不愉快，因为要取消引用它，您必须使用 ! 运算符，当它位于条件表达式内部时，对于某些将其读作 的开发人员来说可能是违反直觉的>逻辑不是。我遇到的另一个问题是 Seq.skip 和 Seq.take 与它们的 Linq 别名不同，因为如果 size 超过序列的大小，它们就会抛出错误。

let batchesOf size (sequence: _ seq) : _ list seq =
    seq {
        let s = ref sequence
        while not (!s |> Seq.isEmpty)  do
            yield !s |> Seq.truncate size |> List.ofSeq
            s := System.Linq.Enumerable.Skip(!s, size)
    }

无论如何，用 F# 重写这个最优雅/最惯用的方法是什么？保持原始行为，但最好没有 ref 可变变量。

Answer 1

使用 seq<_> 类型惯用方式实现此函数很困难 - 该类型本质上是可变的，因此没有简单而良好的功能方法。您的版本效率很低，因为它在序列上重复使用 Skip 。更好的命令选项是使用GetEnumerator并使用IEnumerator迭代元素。您可以在此代码段中找到各种命令式选项： http://fssnip.net/1o

如果您正在学习 F# ，那么最好尝试使用 F# 列表类型编写函数。这样，您就可以使用惯用的函数式风格。然后，您可以使用带有递归和累加器参数的模式匹配来编写 batchesOf ，如下所示：

let batchesOf size input = 
  // Inner function that does the actual work.
  // 'input' is the remaining part of the list, 'num' is the number of elements
  // in a current batch, which is stored in 'batch'. Finally, 'acc' is a list of
  // batches (in a reverse order)
  let rec loop input num batch acc =
    match input with
    | [] -> 
        // We've reached the end - add current batch to the list of all
        // batches if it is not empty and return batch (in the right order)
        if batch <> [] then (List.rev batch)::acc else acc
        |> List.rev
    | x::xs when num = size - 1 ->
        // We've reached the end of the batch - add the last element
        // and add batch to the list of batches.
        loop xs 0 [] ((List.rev (x::batch))::acc)
    | x::xs ->
        // Take one element from the input and add it to the current batch
        loop xs (num + 1) (x::batch) acc
  loop input 0 [] []

作为脚注，使用计算表达式可以使命令式版本更好一点，以便与 < code>IEnumerator，但这不是标准的，而是相当高级的技巧（例如，请参见 http://fssnip.net/37）。

Answer 2

前段时间有朋友问我这个问题。这是一个回收的答案。这有效并且是纯的：

let batchesOf n =
    Seq.mapi (fun i v -> i / n, v) >>
    Seq.groupBy fst >>
    Seq.map snd >>
    Seq.map (Seq.map snd)

或者是不纯的版本：

let batchesOf n =
    let i = ref -1
    Seq.groupBy (fun _ -> i := !i + 1; !i / n) >> Seq.map snd

它们产生一个 seq>。如果您确实必须有一个 'a list list （如示例中所示），那么只需添加 ... |>; Seq.map(List.ofSeq)|> List.ofSeq 如：

> [1..17] |> batchesOf 5 |> Seq.map (List.ofSeq) |> List.ofSeq;;
val it : int list list = [[1; 2; 3; 4; 5]; [6; 7; 8; 9; 10]; [11; 12; 13; 14; 15]; [16; 17]]

希望有帮助！

Answer 3

万岁，我们可以在 F# 4 中使用 List.chunkBySize、Seq.chunkBySize 和 Array.chunkBySize，如 布拉德·柯林斯和斯科特·弗拉斯钦。

Answer 4

如果您愿意，这可以在没有递归的情况下完成，

[0..20] 
    |> Seq.mapi (fun i elem -> (i/size),elem) 
    |> Seq.groupBy (fun (a,_) -> a)
    |> Seq.map (fun (_,se) -> se |> Seq.map (snd));;
val it : seq<seq<int>> =
  seq
    [seq [0; 1; 2; 3; ...]; seq [5; 6; 7; 8; ...]; seq [10; 11; 12; 13; ...];
     seq [15; 16; 17; 18; ...]; ...]

具体取决于您的想法，这可能更容易理解。不过，Tomas 的解决方案可能更惯用 F#

Answer 5

这可能不是惯用的，但它有效：

let batchesOf n l = 
    let _, _, temp', res' = List.fold (fun (i, n, temp, res) hd ->
                                           if i < n then
                                             (i + 1, n, hd :: temp, res)
                                           else
                                             (1, i, [hd], (List.rev temp) :: res)) 
                                       (0, n, [], []) l
    (List.rev temp') :: res' |> List.rev

Answer 6

这是序列的简单实现：

let chunks size (items:seq<_>) =
  use e = items.GetEnumerator()
  let rec loop i acc =
    seq {
      if i = size then 
        yield (List.rev acc)
        yield! loop 0 []
      elif e.MoveNext() then
        yield! loop (i+1) (e.Current::acc)
      else
        yield (List.rev acc)
    }
  if size = 0 then invalidArg "size" "must be greater than zero"
  if Seq.isEmpty items then Seq.empty else loop 0 []

let s = Seq.init 10 id
chunks 3 s 
//output: seq [[0; 1; 2]; [3; 4; 5]; [6; 7; 8]; [9]]

Answer 7

我的方法包括将列表转换为数组并递归地对数组进行分块：

    let batchesOf (sz:int) lt = 
        let arr = List.toArray lt

        let rec bite curr =
            if (curr + sz - 1 ) >= arr.Length then
                [Array.toList arr.[ curr .. (arr.Length - 1)]]
            else
                let curr1 = curr + sz 
                (Array.toList (arr.[curr .. (curr + sz - 1)])) :: (bite curr1)   

        bite 0

    batchesOf 5 [1 .. 17]

    [[1; 2; 3; 4; 5]; [6; 7; 8; 9; 10]; [11; 12; 13; 14; 15]; [16; 17]]

Answer 8

我发现这是一个非常简洁的解决方案：

let partition n (stream:seq<_>) = seq {
    let enum = stream.GetEnumerator()

    let rec collect n partition =
        if n = 1 || not (enum.MoveNext()) then
            partition
        else
            collect (n-1) (partition @ [enum.Current])

    while enum.MoveNext() do
        yield collect n [enum.Current]
}

它作用于一个序列并生成一个序列。输出序列由输入序列中的 n 个元素的列表组成。

Answer 9

您可以使用 Clojure partition 的模拟来解决您的任务下面的 库函数：

let partition n step coll =
    let rec split ss =
        seq {
            yield(ss |> Seq.truncate n)
            if Seq.length(ss |> Seq.truncate (step+1)) > step then
                yield! split <| (ss |> Seq.skip step)
            }
    split coll

用作 partition 5 5 它将为您提供所需的 batchesOf 5 功能：

[1..17] |> partition 5 5;;
val it : seq<seq<int>> =
  seq
    [seq [1; 2; 3; 4; ...]; seq [6; 7; 8; 9; ...]; seq [11; 12; 13; 14; ...];
     seq [16; 17]]

作为高级功能，可以使用n 和 step 您可以使用它来切片重叠批次，也称为滑动窗口，甚至适用于无限序列，如下所示：

Seq.initInfinite(fun x -> x) |> partition 4 1;;
val it : seq<seq<int>> =
  seq
    [seq [0; 1; 2; 3]; seq [1; 2; 3; 4]; seq [2; 3; 4; 5]; seq [3; 4; 5; 6];
     ...]

将其视为仅原型，因为它对源序列进行了许多冗余评估，并且不太适合生产目的。

Answer 10

这个版本通过了我能想到的所有测试，包括惰性求值和单序列求值的测试：

let batchIn batchLength sequence =
    let padding = seq { for i in 1 .. batchLength -> None } 
    let wrapped = sequence |> Seq.map Some
    Seq.concat [wrapped; padding]
    |> Seq.windowed batchLength 
    |> Seq.mapi (fun i el -> (i, el)) 
    |> Seq.filter (fun t -> fst t % batchLength = 0) 
    |> Seq.map snd
    |> Seq.map (Seq.choose id)
    |> Seq.filter (fun el -> not (Seq.isEmpty el))

我对 F# 还很陌生，所以如果我遗漏了任何内容 - 请纠正我，我们将不胜感激。