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

Question

I have in F #, 2 sequences, each of which contains different 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 from a list of integers, List.length equals Seq.length listMaxes , containing numbers elements separated in lists where listMaxes elements limit each group.

For example: called with 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 seems unclean, ugly, imperative and very non-F # -y.

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

Answer 1

This can be done using 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 inspiration from fold and came up with the following solution, which strictly refrains from converting 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 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 2

Here is a version based on the interpretation of the list, which is quite functional in style. You can use Seq.toList to convert between them when you want to handle this. You can also use Seq.scan in combination with Seq.partition ((>=) max) if you want to use only the library functions, but be careful that it is very easy to introduce quadratic complexity in calculations or in memory when doing this.

This is linear for 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 3

I myself found a better implementation. Improvement tips are still welcome.

Working with 2 sequences is really a pain. And I really want to iterate over numbers only once, without turning this sequence into a list. But then I realized that turning listMaxes (usually the shorter of the sequences) is less expensive. Thus, only 1 sequence remains, and I can use Seq.fold over numbers .

What should be the state that we want to save and change when repeating with Seq.fold over numbers ? First, it must include the rest of listMaxes , but the previous highs that we have already surpassed are no longer of interest. Secondly, the accumulated lists are still, although, as in other answers, they can be stored in the reverse order. Moreover: a state is a pair that, as a second element, has an inverse list of inverted lists of numbers.

 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]