Take while running total smaller than value

Question

I am trying to generate a list of even integers while the sum of the items in the list is less equal a given number. For instance if the threshold k is 20, then the expected output is [0;2;4;6;8]

I can generate a list where the largest value is smaller by the threshold like this:

let listOfEvenNumbersSmallerThanTwenty =
    Seq.unfold (fun x -> Some(x, x + 1)) 0 // natural numbers
    |> Seq.filter (fun x -> x % 2 = 0) // even numbers
    |> Seq.takeWhile (fun x -> x <= 20)
    |> List.ofSeq

(I know that I can combine the unfold and filter to Some(x, x + 2) but this task is for educational purposes)

I managed to create a different list with a running total smaller than the threshold:

let runningTotal =
    listOfEvenNumbersSmallerThanTwenty 
    |> Seq.scan (+) 0
    |> Seq.filter (fun x -> x < 20)
    |> List.ofSeq

But in order to do that, I have set the threshold in listOfEvenNumbersSmallerThanTwenty (which is way more than the items needed) and I have lost the initial sequence. I did also try to find that using a mutable value but didn't really like that route.

Answer 1

You can create a small predicate function that will encapsulate a mutable sum.

let sumLessThan threshold =
    let mutable sum = 0
    fun x ->
        sum <- sum + x
        sum < threshold

Usage is very simple and it can be applied to any sequence

Seq.initInfinite ((*) 2) |> Seq.takeWhile (sumLessThan 20)

There is nothing bad in using mutable state when its encapsulated (check usages of the mutable variable in Seq module)

Answer 2

Here's a solution that I think is pretty elegant (although not the most efficient):

let evens = Seq.initInfinite (fun i -> 2 * i)
Seq.initInfinite (fun i -> Seq.take i evens)
    |> Seq.takeWhile (fun seq ->
        Seq.sum seq <= 20)
    |> Seq.last
    |> List.ofSeq