If you want to implement this over IEnumerable<'T>
(to make it lazy), then it is necessarily going to be somewhat imperative, because the IEnumerator<'T>
type that is used to iterate over the input is imperative. But the rest can be written as a recursive function using sequence expressions.
The following is lazy in the first level (it produces each group lazily), but it does not produce elements of the group lazily (I think that would have pretty subtle semantics):
/// Group adjacent elements of 'input' according to the
/// keys produced by the key selector function 'f'
let groupAdjacent f (input:seq<_>) = seq {
use en = input.GetEnumerator()
// Iterate over elements and keep the key of the current group
// together with all the elements belonging to the group so far
let rec loop key acc = seq {
if en.MoveNext() then
let nkey = f en.Current
if nkey = key then
// If the key matches, append to the group so far
yield! loop key (en.Current::acc)
else
// Otherwise, produce the group collected so far & start a new one
yield List.rev acc
yield! loop nkey [en.Current]
else
// At the end of the sequence, produce the last group
yield List.rev acc
}
// Start with the first key & first value as the accumulator
if en.MoveNext() then
yield! loop (f en.Current) [en.Current] }
Unfortunately, this (pretty useful!) function is not included in the standard F# library, so if you want to group adjacent elements (rather than arbitrary elements in the list using Seq.groupBy
), you have to define it yourself...