如何在 F# 中对顺序值进行分组

Question

让我们考虑以下排序数据：

[1; 2; 3; 5; 6; 20; 21; 22; 23]

我想得到：

[ [1; 2; 3]; [5; 6]; [20; 21; 22; 23] ]

实现此目标的最佳方法是什么？（列表最多 1000 个条目）。

Answer 1

所以你是在暗示你想根据两个连续值之间的差应该是 1 的条件进行分组。或者从另一个角度来看，当差不是 1 时拆分。

可以找到按谓词对列表进行分组的示例 and here。考虑输入序列而不是列表，我们可能会从我们能够懒惰地使用它的事实中得到一些好处。

let splitWhen condition (source : seq<'T>) : seq<'T[]> = seq {
    let stateref, acc = ref None, ResizeArray()
    use ie = source.GetEnumerator()
    while ie.MoveNext() do
        let current = ie.Current
        match !stateref with
        | Some previous when condition previous current ->
            yield acc.ToArray()
            acc.Clear()
        | _ -> ()
        acc.Add current
        stateref := Some current
    if acc.Count > 0 then
        yield acc.ToArray() }

[1; 2; 3; 5; 6; 20; 21; 22; 23]
|> splitWhen (fun x0 x1 -> x1 - x0 <> 1)
// val it : seq<int []> = seq [[|1; 2; 3|]; [|5; 6|]; [|20; 21; 22; 23|]]

Answer 2

let group ls =
    [
        let mutable last = 0
        let mutable current = []
        for x in ls do
            if x > (last + 1) then
                if not current.IsEmpty then
                    yield current |> List.rev
                current <- [x]
            else
                current <- x :: current
            last <- x
        if not current.IsEmpty then
            yield current |> List.rev
    ]

group [1; 2; 3; 5; 6; 20; 21; 22; 23]
val it : int list list = [[1; 2; 3]; [5; 6]; [20; 21; 22; 23]]

Answer 3

这里的版本可能更加地道，至少对我而言，更具可读性。它仅依赖于 List 模块中的标准函数 foldBack 并且完全避免了可变性。

let group ls =
    (ls, [])
    ||> List.foldBack (fun l s ->
        match s with 
        | [] | [[]] -> [[l]]
        | (n::res)::ns ->
            if n = l+1
            then (l::n::res)::ns
            else [l]::(n::res)::ns)

也可以重构为更通用的函数

let chunkBy cond ls =
    (ls, [])
    ||> List.foldBack (fun l s ->
        match s with 
        | [] | [[]] -> [[l]]
        | (n::res)::ns ->
            if cond l n
            then (l::n::res)::ns
            else [l]::(n::res)::ns)

let group = chunkBy (fun prev next -> prev + 1 = next)

请注意，这利用了仅在列表上实现的缺点运算符 ::。 cons 运算符将一个项目添加到列表中，这就是该函数使用 foldBack.

的原因

Answer 4

这是一个将输入列表折叠成新列表并根据需要分组的实现。

let group l =
  let addNextInt (i : int) (l : List<List<int>>) =
    match l with
    | [] -> [[i]]
    | (x::xs)::tail ->
        if x - i = 1 then (i::x::xs)::tail
        else [i]::(x::xs)::tail
    | _ -> failwith "Unreachable"

  List.foldBack addNextInt l []

// Input: [], Output: []
// Input: [1; 2], Output: [[1; 2]]
// Input: [1; 3], Output: [[1]; [3]]
// Input: [1; 3; 5; 6], Output: [[1]; [3]; [5; 6]]
// Input: [1; 2; 3; 5; 6; 20; 21; 22; 23], Output: [[1; 2; 3]; [5; 6]; [20; 21; 22; 23]]

如何在 F# 中对顺序值进行分组

how can I group sequential values, in F#

f#