Partitioning a list in F# based on whole group characteristics I only started programming in F# yesterday, so I've not yet discovered what idiomatic F# actually looks like.

The first task I set myself required partitioning a list into smaller lists but where the partitioning is based on the characteristics of the whole group, rather than just being able to find split points based on the current element.

For example, given the list [1;2;3;4;5], I might want to group into sub-lists when the sum of the sub-list has reached at least 5. This would result in the output [[1;2;3]; [4;5]].

Any remaining elements that don't meet the criteria would be in a final sub-list.

My first attempt is below:

module Test

let rec partitionOn groupComplete list =
    let take list n = Seq.take n list

    // Take items from the front of the list until they form a complete group
    // or there are no more items
    let firstGroupAndRemainder itemsList =
        let firstGroup =
            [0 .. List.length itemsList]
            |&gt; Seq.map (take itemsList)
            |&gt; Seq.tryFind groupComplete
        match firstGroup with
        | Some g -&gt;
            let groupList = g |&gt; Seq.toList
            let remainingList = Seq.skip (List.length groupList) itemsList |&gt; Seq.toList
            (groupList, remainingList)
        | None -&gt; (itemsList, [])

    match list with
    | [] -&gt; []
    | _ -&gt;
        let group, rest = firstGroupAndRemainder list
        [group] @ partitionOn groupComplete rest

[&lt;EntryPoint&gt;]
let main argv =
    // Groups with sum greater than 5 (plus remaining elements)
    let result1 = partitionOn (fun l -&gt; Seq.sum l &gt; 5) [1;5;2;6;2]
    printfn "result1: %A" result1 // [[1;5]; [2;6]; [2]]

    // Groups with length 3 (plus remaining elements)
    let result2 = partitionOn (fun l -&gt; Seq.length l = 3) [1;5;2;6;2]
    printfn "result2: %A" result2  // [[1;5;2]; [6;2]]

    0


It feels like there should be a simpler way to achieve this but I haven't yet thought of it.

Update

I've discovered the defaultArg function, so the firstGroupAndRemainder function might be slightly tidier as:

let firstGroupAndRemainder itemsList =
    let firstGroup =
        [0 .. List.length itemsList]
        |&gt; Seq.map (take itemsList)
        |&gt; Seq.tryFind groupComplete
    let groupList = (defaultArg firstGroup (List.toSeq itemsList)) |&gt; Seq.toList
    let remainingList = Seq.skip (List.length groupList) itemsList |&gt; Seq.toList
    (groupList, remainingList)
Based on this answer from the Haskell version of this question, it looks like we can do something as simple as:

let partitionOn groupComplete list =
    let rec inner currentGroup remainingList =
        match (currentGroup, remainingList) with
        | (group, []) -&gt; [group]
        | (group, remaining) when groupComplete group -&gt; [group] @ (inner [] remaining)
        | (group, head::tail) -&gt; inner (group @ [head]) tail
    inner [] list


This simply recursively handles the three cases of: running out of elements; having a complete group; and building a group.

Update

Henrik Hansen pointed out that it is preferable to have a tail-recursive function. One possible way of achieving this is:

let partitionOn groupComplete list =
    let rec inner currentGroup remainingList =
        match remainingList with
        | [] -&gt; [currentGroup]
        | head::tail -&gt;
            let complete = groupComplete currentGroup
            let additionalGroup = if complete then [currentGroup] else []
            let newCurrentGroup = if complete then [] else currentGroup @ [head]
            let newRemaining = if complete then remainingList else tail
            additionalGroup @ (inner newCurrentGroup newRemaining)
    inner [] list


This merges together the last two cases of the match and gives a single call to inner at the end.

Update 2

If we look at the IL for this version, we can see that it is tail recursive:

    ...
    IL_0069: tail.
    IL_006b: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!!0&gt; [FSharp.Core]Microsoft.FSharp.Core.Operators::op_Append&lt;class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!!a&gt;&gt;(class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!!0&gt;, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!!0&gt;)
    IL_0070: ret
    IL_0071: ldarg.1
    IL_0072: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!0&gt; class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!!a&gt;&gt;::get_Empty()
    IL_0077: call class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!0&gt; class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!!a&gt;&gt;::Cons(!0, class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1&lt;!0&gt;)
    IL_007c: ret
} // end of method _::'inner@2-5'


Update 3

Nice idea to use a fold, from TheQuickBrownFox. This can be done more simply using the built-in fold function, keeping the same API:

let partitionOn groupComplete list =
    let folder acc x =
        match List.rev acc with
        | [] -&gt; [[x]]
        | current::rest when groupComplete current -&gt; acc @ [[x]]
        | current::rest -&gt; (List.rev rest) @ [current @ [x]]
    List.fold folder [] list


However, @ is O(n), whereas :: is O(1), so it should really be:

let partitionOn groupComplete list =
    let folder acc x =
        match acc with
        | [] -&gt; [[x]]
        | current::rest when groupComplete current -&gt; [x]::acc
        | current::rest -&gt; (x::current)::rest
    List.fold folder [] list |&gt; List.map List.rev |&gt; List.rev


Update 4

Based on TheQuickBrownFox comment the fold could be modified as follows:

let partitionOn initialGroupValue groupUpdate groupComplete list =
    let folder acc x =
        match acc with
        | ([], score) -&gt; ([[x]], groupUpdate score x)
        | (a, score) when groupComplete score -&gt; ([x]::a, groupUpdate initialGroupValue x)
        | (current::rest, score) -&gt; ((x::current)::rest, groupUpdate score x)
    List.fold folder ([], initialGroupValue) list |&gt; fst |&gt; List.map List.rev |&gt; List.rev


This version separates the current group evaluation into an update and a test, so that the minimum change is made for each iteration of the fold and the whole group doesn't need to be recalculated each time.