CODEWITHSUNDEEP
f#
Thomas
Thomas

Reputation: 12107

how can I group sequential values, in F#

let's consider the following SORTED data:

[1; 2; 3; 5; 6; 20; 21; 22; 23]

and I would like to get:

[ [1; 2; 3]; [5; 6]; [20; 21; 22; 23] ]

what would be the best way to achieve this? (the list is at most 1000 entries).

Upvotes: 2

Views: 163

Answers (4)

Roland Andrag
Roland Andrag

Reputation: 462

Here is an implementation which folds the input list into a new list, grouping as required.

let group l =
  let addNextInt (i : int) (l : List<List<int>>) =
    match l with
    | [] -> [[i]]
    | (x::xs)::tail ->
        if x - i = 1 then (i::x::xs)::tail
        else [i]::(x::xs)::tail
    | _ -> failwith "Unreachable"

  List.foldBack addNextInt l []

// Input: [], Output: []
// Input: [1; 2], Output: [[1; 2]]
// Input: [1; 3], Output: [[1]; [3]]
// Input: [1; 3; 5; 6], Output: [[1]; [3]; [5; 6]]
// Input: [1; 2; 3; 5; 6; 20; 21; 22; 23], Output: [[1; 2; 3]; [5; 6]; [20; 21; 22; 23]]

Upvotes: 1

torbonde
torbonde

Reputation: 2459

Here's a version which is perhaps a bit more idiomatic and, to me at least, a bit more readable. It relies only on the standard function foldBack in the List module and avoids mutability entirely.

let group ls =
    (ls, [])
    ||> List.foldBack (fun l s ->
        match s with 
        | [] | [[]] -> [[l]]
        | (n::res)::ns ->
            if n = l+1
            then (l::n::res)::ns
            else [l]::(n::res)::ns)

It may also be refactored into a more general function

let chunkBy cond ls =
    (ls, [])
    ||> List.foldBack (fun l s ->
        match s with 
        | [] | [[]] -> [[l]]
        | (n::res)::ns ->
            if cond l n
            then (l::n::res)::ns
            else [l]::(n::res)::ns)

let group = chunkBy (fun prev next -> prev + 1 = next)

Notice that this leverages the cons operator :: which is only implemented on lists. The cons operator prepends an item to a list, which is why the function uses foldBack.

Upvotes: 4

citykid
citykid

Reputation: 11060

let group ls =
    [
        let mutable last = 0
        let mutable current = []
        for x in ls do
            if x > (last + 1) then
                if not current.IsEmpty then
                    yield current |> List.rev
                current <- [x]
            else
                current <- x :: current
            last <- x
        if not current.IsEmpty then
            yield current |> List.rev
    ]

group [1; 2; 3; 5; 6; 20; 21; 22; 23]
val it : int list list = [[1; 2; 3]; [5; 6]; [20; 21; 22; 23]]

Upvotes: 1

kaefer
kaefer

Reputation: 5741

So you're implying you want to group by the condition that the difference between two consecutive values should be 1. Or viewed the other way, to split when the difference is other than 1.

Examples for grouping lists by predicate can be found here and here. Considering an input sequence as opposed to a list, we might get some mileage out of the fact that we are able to consume it lazily.

let splitWhen condition (source : seq<'T>) : seq<'T[]> = seq {
    let stateref, acc = ref None, ResizeArray()
    use ie = source.GetEnumerator()
    while ie.MoveNext() do
        let current = ie.Current
        match !stateref with
        | Some previous when condition previous current ->
            yield acc.ToArray()
            acc.Clear()
        | _ -> ()
        acc.Add current
        stateref := Some current
    if acc.Count > 0 then
        yield acc.ToArray() }

[1; 2; 3; 5; 6; 20; 21; 22; 23]
|> splitWhen (fun x0 x1 -> x1 - x0 <> 1)
// val it : seq<int []> = seq [[|1; 2; 3|]; [|5; 6|]; [|20; 21; 22; 23|]]

Upvotes: 0

Related Questions