"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 就像折叠，只是它 return 是一系列连续的状态值。您可以 return 一对 (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

我用这个：

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 3

这是我对 Lee 的回答的 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 }
}

I put my code with some tests on gist.

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]

因为没有指定列表不够大时 return 的内容，在这种情况下它将 return 向量：[sum-of-the-array original-array]。

当然可以很容易地改变。

"pick from beginning of a list and reduce until the result satisfies a predicate" 是否有函数式编程习惯用法？

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

language-agnostic

functional-programming

idioms