f# - How to partition a list with a given group size?

Question

I'm looking for the best way to partition a list (or seq) so that groups have a given size. for ex. let's say I want to group with size 2 (this could be any other number though):

let xs = [(a,b,c); (a,b,d); (y,z,y); (w,y,z); (n,y,z)]
let grouped = partitionBySize 2 input
// => [[(a,b,c);(a,b,d)]; [(y,z,y);(w,y,z)]; [(n,y,z)]]

The obvious way to implement partitionBySize would be by adding the position to every tuple in the input list so that it becomes

[(0,a,b,c), (1,a,b,d), (2,y,z,y), (3,w,y,z), (4,n,y,z)]

and then use GroupBy with

xs |> Seq.ofList |> Seq.GroupBy (function | (i,_,_,_) -> i - (i % n))

However this solution doesn't look very elegant to me. Is there a better way to implement this function (maybe with a built-in function)?

Answer 1

This seems to be a repeating pattern that's not captured by any function in the F# core library. When solving similar problems earlier, I defined a function Seq.groupWhen (see F# snippets) that turns a sequence into groups. A new group is started when the predicate holds.

You could solve the problem using Seq.groupWhen similarly to Seq.group (by starting a new group at even index). Unlike with Seq.group, this is efficient, because Seq.groupWhen iterates over the input sequence just once:

[3;3;2;4;1;2;8] 
|> Seq.mapi (fun i v -> i, v) // Add indices to the values (as first tuple element)
|> Seq.groupWhen (fun (i, v) -> i%2 = 0) // Start new group after every 2nd element
|> Seq.map (Seq.map snd) // Remove indices from the values

Implementing the function directly using recursion is probably easier - the solution from John does exactly what you need - but if you wanted to see a more general approach then Seq.groupWhen may be interesting.