是否有一个函数式编程习惯用于"从列表的开头选择并减少直到结果满足谓词"？

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接下来的a 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