Is there a functional programming idiom for "pick from beginning of a list and reduce until the result satisfies a predicate"?

Question

Suppose I have a list of numbers, and I need to know how many elements I would have to pick from the beginning of it to get at least the desired sum.

The algorithm is trivial: I pick numbers from the beginning of the list until the sum of all picked numbers exceeds some amount.

I could write it in imperative style like this:

fun pickEnough(list: List<Double>, enough: Double): List<Double>? {
    var soFar = 0.0
    var index = 0
    for (index in 0..list.size) {
        soFar += list[index]
        if (soFar > enough) {
            return list.subList(0, index)
        }
    }
    return null
}

An inefficient, but more general solution would be to generate all the possible sublists and pick the first one whose reduction result is good enough:

fun <T> pickEnough(list: List<T>, reducer: (T, T) -> T, enough: (T) -> Boolean): List<T>? =
list.indices
    .map { index -> list.sublist(0, index) }
    .first { sublist -> enough(sublist.reduce(reducer)) }

pickEnough(listOf(5,8,0,0,8), { a, b -> a + b}, { it > 10 }) // [5, 8]

Is there an established functional idiom for this, or maybe a combination of such that are better in performance and expressiveness than my attempt at generalizing this piece?

The example is in Kotlin, but I would prefer a language-agnostic answer, although answers in any language are appreciated, as long as they present higher-level idioms that describe this operation.

Answer 1

What you want is a scan followed by a takeWhile. scan is like a fold except it returns a sequence of successive state values. You can return successive states of a pair (x, soFar) which contain the current value in the sequence and the current running total. You can then take as many from this sequence where the current value has not caused the desired total to be exceeded. For example in F# you could do:

let pickEnough (l: seq<double>) (enough: double): seq<double> =
    Seq.scan (fun (_, soFar) x -> (x, x+soFar)) (0.0, 0.0) l |> 
    Seq.skip 1 |> 
    Seq.takeWhile (fun (x, soFar) -> soFar - x < enough) |> 
    Seq.map fst

Answer 2

Here's my Kotlin version of Lee's answer:

fun <A, B> Iterable<A>.scanl(initial: B, f: (B, A) -> B): List<B> {
   return listOf(initial).plus(if (this.count() == 0) {
       emptyList()
   } else {
       this.drop(1).scanl(f(initial, this.first()), f)
   })
}

fun pickEnough(list: List<Int>, enough: Int): List<Int>? {
    return list
      .scanl(0 to 0) {
        pair, x ->
        x to (x + pair.second)
      }
      .drop(1)
      .takeWhile {
        pair ->
        val (x, soFar) = pair
        soFar - x < enough
      }
      .map { it.first }
}

I put my code with some tests on gist.