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

Question

I have, in F#, 2 sequences, each containing distinct integers, strictly in ascending order: listMaxes and numbers.

If not Seq.isEmpty numbers, then it is guaranteed that not Seq.isEmpty listMaxes and Seq.last listMaxes >= Seq.last numbers.

I would like to implement in F# a function that returns a list of list of integers, whose List.length equals Seq.length listMaxes, containing the elements of numbers divided in lists, where the elements of listMaxes limit each group.

For example: called with the arguments

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

this function should return

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

I can implement this function, iterating over numbers only once:

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
                })
        })

But this code feels unclean, ugly, imperative, and very un-F#-y.

Is there any functional / F#-idiomatic way to achieve this?

Answer 1

Here's a version based on list interpretation, which is quite functional in style. You can use Seq.toList to convert between them, whenever you want to handle that. You could also use Seq.scan in conjunction with Seq.partition ((>=) max) if you want to use only library functions, but beware that it's very very easy to introduce a quadratic complexity in either computation or memory when doing that.

This is linear in both:

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

It can be done like this with pattern matching and tail recursion:

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)

Update: I also got inspired by fold and came up with the following solution that strictly refrains from converting the input sequences.

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