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

Question

我在F#中有两个序列,每个序列都包含不同的整数,严格按升序排列:listMaxes和numbers.

如果not Seq.isEmpty numbers,则保证not Seq.isEmpty listMaxes和Seq.last listMaxes >= Seq.last numbers.

我想在F#中实现一个函数,它返回一个整数列表的列表,它的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 ]

这个功能应该返回

[ [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#.

是否有任何功能/ F#-idiomatic方法来实现这一目标？

Answer 1

可以通过模式匹配和尾递归来完成：

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