如何以惯用的方式基于另一个序列拆分 F# 中的序列

Question

我在 F# 中有 2 个序列，每个序列包含不同的整数，严格按升序排列：listMaxes 和 numbers。

如果not Seq.isEmpty numbers，那么保证not Seq.isEmpty listMaxes和Seq.last listMaxes >= Seq.last numbers.

我想在 F# 中实现一个函数，该函数 return 是一个整数列表，其 List.length 等于 Seq.length listMaxes，包含 numbers 的元素在列表中，listMaxes 的元素限制了每个组。

例如：用参数调用

listMaxes = seq [ 25; 56; 65; 75; 88 ]
numbers = seq [ 10; 11; 13; 16; 20; 25; 31; 38; 46; 55; 65; 76; 88 ]

这个函数应该return

[ [10; 11; 13; 16; 20; 25]; [31; 38; 46; 55]; [65]; List.empty; [76; 88] ]

我可以实现这个功能，只迭代 numbers 一次：

let groupByListMaxes listMaxes numbers = 
    if Seq.isEmpty numbers then
        List.replicate (Seq.length listMaxes) List.empty
    else
        List.ofSeq (seq {
            use nbe = numbers.GetEnumerator ()
            ignore (nbe.MoveNext ())
            for lmax in listMaxes do
                yield List.ofSeq (seq {
                    if nbe.Current <= lmax then
                        yield nbe.Current
                    while nbe.MoveNext () && nbe.Current <= lmax do
                        yield nbe.Current
                })
        })

但是这段代码感觉不干净、丑陋、命令式，而且非常不符合 F#-y。

是否有任何功能性/F# 惯用的方法来实现此目的？

Answer 1

这是一个基于列表解释的版本，在风格上非常实用。你可以使用 Seq.toList 在它们之间进行转换，只要你想处理它。如果您只想使用库函数，也可以将 Seq.scan 与 Seq.partition ((>=) max) 结合使用，但请注意，这样做时很容易在计算或内存中引入二次复杂度。

两者都是线性的：

let splitAt value lst =
    let rec loop l1 = function
        | []                    -> List.rev l1, []
        | h :: t when h > value -> List.rev l1, (h :: t)
        | h :: t                -> loop (h :: l1) t
    loop [] lst

let groupByListMaxes listMaxes numbers =
    let rec loop acc lst = function
        | []     -> List.rev acc
        | h :: t ->
            let out, lst' = splitAt h lst
            loop (out :: acc) lst' t
    loop [] numbers listMaxes

Answer 2

可以这样用模式匹配和尾递归来完成：

let groupByListMaxes listMaxes numbers =
    let rec inner acc numbers =
        function
        | [] -> acc |> List.rev
        | max::tail ->
            let taken = numbers |> Seq.takeWhile ((>=) max) |> List.ofSeq
            let n = taken |> List.length
            inner (taken::acc) (numbers |> Seq.skip n) tail

    inner [] numbers (listMaxes |> List.ofSeq)

更新：我也受到fold的启发，提出了以下解决方案，严格避免转换输入序列。

let groupByListMaxes maxes numbers =
    let rec inner (acc, (cur, numbers)) max = 
        match numbers |> Seq.tryHead with
        // Add n to the current list of n's less
        // than the local max
        | Some n when n <= max ->
            let remaining = numbers |> Seq.tail  
            inner (acc, (n::cur, remaining)) max
        // Complete the current list by adding it
        // to the accumulated result and prepare
        // the next list for fold.
        | _ ->
            (List.rev cur)::acc, ([], numbers)

    maxes |> Seq.fold inner ([], ([], numbers)) |> fst |> List.rev

Answer 3

我自己找到了更好的实现方式。仍然欢迎提出改进建议。

处理2个序列真的很痛苦。而且我真的只想迭代 numbers 一次而不将该序列变成列表。但后来我意识到转向 listMaxes（通常是较短的序列）成本更低。这样只剩下 1 个序列，我可以使用 Seq.fold 而不是 numbers。

在 Seq.fold 迭代 numbers 时，我们想要保留和更改的状态应该是什么？首先，它肯定应该包括 listMaxes 的剩余部分，但我们已经超过的先前最大值不再有意义。其次，到目前为止累积的列表，尽管与其他答案一样，这些列表可以倒序保存。更重要的是：状态是一对，它的第二个元素是到目前为止数字的反转列表的反转列表。

let groupByListMaxes listMaxes numbers =
    let rec folder state number =
        match state with
            | m :: maxes, _ when number > m ->
                folder (maxes, List.empty :: snd state) number
            | m :: maxes, [] ->
                fst state, List.singleton (List.singleton number)
            | m :: maxes, h :: t ->
                fst state, (number :: h) :: t
            | [], _ ->
                failwith "Guaranteed not to happen"
    let listMaxesList = List.ofSeq listMaxes
    let initialState = listMaxesList, List.empty
    let reversed = snd (Seq.fold folder initialState numbers)
    let temp = List.rev (List.map List.rev reversed)
    let extraLength = List.length listMaxesList - List.length temp
    let extra = List.replicate extraLength List.empty
    List.concat [temp; extra]

Answer 4

我知道这是一个老问题，但我遇到了一个非常相似的问题，我认为这是一个简单的解决方案：

let groupByListMaxes cs xs =
    List.scan (fun (_, xs) c -> List.partition (fun x -> x <= c) xs)
        ([], xs)
        cs
    |> List.skip 1
    |> List.map fst

如何以惯用的方式基于另一个序列拆分 F# 中的序列

How to split a sequence in F# based on another sequence in an idiomatic way

f#

sequences