functional-programming - 是否有 "pick from beginning of a list and reduce until the result satisfies a predicate"的功能性编程习惯用法？

Question

假设我有一个数字列表，并且我需要知道从一开始就必须选择多少个元素才能至少获得所需的总和。

该算法很简单:我从列表的开头选择数字，直到所有选择的数字之和超过一定数量为止。

我可以这样写命令式的代码:

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
}

一种低效但更通用的解决方案是生成所有可能的子列表，并选择第一个其缩减结果足够好的子列表:

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]

是否有既定的功能惯用法，或者可能是组合的用法或功能组合，这些惯用法比我对本文的概括更胜一筹？

该示例在Kotlin中进行，但我更喜欢与语言无关的答案，尽管可以接受任何语言的答案，只要它们呈现了描述此操作的高级成语即可。

Answer 1

您想要的是一个scan和一个takeWhile。 scan类似于折叠，但它返回一系列连续的状态值。您可以返回一对(x, soFar)的连续状态，这些状态包含序列中的当前值和当前运行总计。然后，您可以从该序列中获取尽可能多的数据，其中当前值未导致超出期望的总数。例如，在F#中，您可以执行以下操作:

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