Gibt es eine funktionale Programmiersprache für "vom Anfang einer Liste auswählen und reduzieren, bis das Ergebnis ein Prädikat erfüllt"?

Question

Angenommen, ich habe eine Liste von Zahlen, und ich muss wissen, wie viele Elemente ich von Anfang an auswählen müsste, um mindestens die gewünschte Summe zu erhalten.

Der Algorithmus ist trivial: Ich wähle Zahlen vom Anfang der Liste, bis die Summe aller ausgewählten Zahlen einen bestimmten Betrag übersteigt.

ich es in imperativen Stil so schreiben könnte:

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 
} 

Eine ineffiziente, aber allgemeinere Lösung alle möglichen Teil-Listen generieren würde und die erste, deren Reduktion Pick Ergebnis ist gut genug:

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] 

Gibt es ein festgelegtes funktionales Idiom dafür, oder vielleicht eine Kombination von solchen, die in der Leistung und Ausdruckskraft besser sind als mein Versuch, dieses Stück zu verallgemeinern?

Das Beispiel ist in Kotlin, aber ich würde eine sprachunabhängige Antwort bevorzugen, obwohl Antworten in jeder Sprache geschätzt werden, solange sie höhere Idiome darstellen, die diese Operation beschreiben.

Answer 1

Was Sie wollen, ist ein scan gefolgt von einem . scan ist wie eine Falte, außer dass es eine Folge aufeinanderfolgender Statuswerte zurückgibt. Sie können aufeinanderfolgende Zustände eines Paares (x, soFar) zurückgeben, die den aktuellen Wert in der Sequenz und die aktuelle laufende Summe enthalten. Sie können dann aus dieser Sequenz so viele entnehmen, dass der aktuelle Wert nicht dazu geführt hat, dass die gewünschte Summe überschritten wurde. Zum Beispiel in F # könnten Sie tun:

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

Ich benutze diese:

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

Hier ist meine Kotlin Version von Lee Antwort:

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

In Clojure ist a reduced Funktion:

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

Da, was zurückgegeben werden soll, wenn die Liste nicht groß genug ist, wurde nicht angegeben, es wird in diesem Fall einen Vektor zurückgeben: [sum-of-the-array original-array].

Das könnte natürlich leicht geändert werden.