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

假设我有一个数字列表，我需要知道有多少元素，我将不得不从它的开始选择至少得到所需的总和。

该算法是微不足道的：我从列表的开头挑选数字，直到所有选取的数字之和超过一定数量。

我可以这样写：

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 

Answer 2

这是我的Kotlin版本的李的答案：

 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 } } 

我把一些测试的代码放在要点上。

Answer 3

我使用这个：

 fun IntArray.pickEnough(initV: Int, reducer: (Int, Int) -> Int, predicate: (Int) -> Boolean): List<Int> { var sum = initV return list.takeWhile { sum = reducer(sum, it) predicate(sum) } } 

Answer 4

在Clojure中有一个reduced函数：

 ;; Clojure (reduce (fn [[sum list] el] (if (< 10 sum) (reduced list) [(+ sum el) (conj list el)])) [0 []] [5 8 0 0 8]) ;; => [5 8] 

由于如果列表不够大，没有指定返回值，在这种情况下将返回一个向量： [sum-of-the-array original-array] 。

那当然可以很容易地改变。