Gibt es in der funktionalen Programmierung ein Konzept für 'falten mit Pause' oder 'mit Akku finden'?

Question

Titel sagt alles, wirklich; Das Iterieren über die Sammlung, während der Status zwischen den Schleifen beibehalten wird, und das Beenden der Iteration basierend auf der Beendigungsbedingung sowie das einfache Auslaufen von Elementen kann das gebräuchlichste Muster sein, um irgendetwas in der imperativen Programmierung zu erreichen. Es scheint mir jedoch, wie es etwas funktionelle gentleprogrammers ist vereinbart über oder zumindest zu sprechen Ich traf nie ein Idiom für sie oder ein halb-genormte Namen wie mit map, fold, reduce usw.

ich oft verwenden die followinig Code in scala:

implicit class FoldWhile[T](private val items :Iterable[T]) extends AnyVal { 
    def foldWhile[A](start :A)(until :A=>Boolean)(op :(A, T)=>A) :A = { 
     if (until(start)) start 
     else { 
      var accumulator = start 
      items.find{ e => accumulator = op(accumulator, e); until(accumulator) } 
      accumulator 
     } 

    } 

} 

Aber es ist hässlich. Jedes Mal, wenn ich einen deklarativen Ansatz versuche, komme ich mit noch mehr und fast sicher langsamem Code, ähnlich:

Iterator.iterate((start, items.iterator)){ 
    case (acc, i) if until(acc) => (acc, i) 
    case (acc, i) if i.hasNext => (op(acc, i.next()), i) 
    case x => x 
}.dropWhile { 
    case (acc, i) => !until(acc) && i.hasNext 
}.next()._1 

(Eine funktionelle Variante List s oder Stream s verwenden würde, aber Iteratoren haben wohl weniger Overhead als die Umwandlung items zu einem Stream, als Standard-Implementierung für letztere verwendet sowieso einen Iterator darunter).

Meine Fragen sind:

1) Ist dieses Konzept einen Namen in der funktionalen Programmierung hat, und wenn ja, was ist das Muster mit der Umsetzung verbunden?

2) Was wäre der beste (d. H. Prägnante, generische, faule und am wenigsten Overhead) Weg, es in scala zu implementieren?

Answer 1

Dies ist verpönt von scala-Puristen, aber Sie können eine return Anweisung wie folgt verwendet werden:

def foldWhile[A](zero: A)(until:A => Boolean)(op: (A,T) => A): A = items.fold(zero) { 
     case (a, b) if until(a) => return a 
     case (a,b) => op(a, b) 
} 

Oder, wenn Sie einer von denen sind Stirnrunzeln, und eine rein funktionale Lösung ohne schmutzige Imperativ Tricks möchte Sie können etwas faul, wie ein Iterator oder einen Stream verwenden:

items 
    .toStream // or .iterator - it doesn't really matter much in this case 
    .scanLeft(zero)(op) 
    .find(until) 

Answer 2

Die funktionale Möglichkeit, solche Dinge zu tun, ist über Tail Recursion:

implicit class FoldWhile[T](val items: Iterable[T]) extends AnyVal { 

    def foldWhile[A](zero: A)(until: A => Boolean)(op: (A, T) => A): A = { 
    @tailrec def loop(acc: A, remaining: Iterable[T]): A = 
     if (remaining.isEmpty || !until(acc)) acc else loop(op(acc, remaining.head), remaining.tail) 

    loop(zero, items) 
    } 
} 

Rekursion Verwenden Sie bei jedem Schritt entscheiden können, ob Sie break ohne Verwendung und ohne Overhead, weil Schwanz Rekursion gehen oder nicht wollen werden vom Compiler in Iterationen konvertiert.

Auch Mustererkennung wird oft verwendet, um Sequenzen zu zerlegen. Zum Beispiel könnten, wenn Sie ein List haben Sie tun:

implicit class FoldWhile[T](val items: List[T]) extends AnyVal { 

    def foldWhile[A](zero: A)(until: A => Boolean)(op: (A, T) => A): A = { 
    @tailrec def loop(acc: A, remaining: List[T]): A = remaining match { 
     case Nil    => acc 
     case _ if !until(acc) => acc 
     case h :: t   => loop(op(acc, h), t) 
    } 

    loop(zero, items) 
    } 
} 

Scala hat die @scala.annotation.tailrec Anmerkung zu Kraft Kompilierung fehlschlagen, wenn die Funktion, die Sie mit Anmerkungen versehen nicht Schwanz ist rekursiv. Ich schlage vor, dass Sie es so oft wie möglich verwenden, da es sowohl Fehler vermeidet als auch den Code dokumentiert.

Answer 3

eine rechte Falte, wenn träge gemacht, kann die vorzeitige Beendigung tun.In Haskell, zum Beispiel, können Sie die find Funktion (Return erste Element der Liste, die Prädikat erfüllt) schreiben mit foldr:

find :: (a -> Bool) -> [a] -> Maybe a 
find p = foldr (\a r -> if p a then Just a else r) Nothing 

-- For reference: 
foldr :: (a -> r -> r) -> r -> [a] -> r 
foldr _ z [] = [] 
foldr f z (a:as) = f a (foldr f z as) 

Was passiert, wenn Sie versuchen, sagen wir, find even [1..]? (Beachten Sie, dass dies eine unendliche Liste!)

find even [1..] 
    = foldr (\a r -> if even a then Just a else r) Nothing [1..] 
    = if even 1 
    then Just 1 
    else foldr (\a r -> if even a then Just a else r) Nothing ([2..]) 
    = if False 
    then Just 1 
    else foldr (\a r -> if even a then Just a else r) Nothing ([2..]) 
    = foldr (\a r -> if even a then Just a else r) Nothing ([2..]) 
    = if even 2 
    then Just 2 
    else foldr (\a r -> if even a then Just a else r) Nothing ([3..]) 
    = if True 
    then Just 2 
    else foldr (\a r -> if even a then Just a else r) Nothing ([3..]) 
    = Just 2 

Laziness bedeutet, dass die Funktion, die wir mit (\a r -> if even a then Just a else r) falten zu entscheiden, ob bekommt das r Argument das eine zwingen, deren Auswertung erfordert, dass wir die Liste rekursiv -überhaupt. Wenn also even 2 zu True ausgewertet wird, wählen wir den Zweig if ... then ... else ... aus, der das Ergebnis, das vom Ende der Liste berechnet wurde, verwirft - was bedeutet, dass wir es nie auswerten. (Es läuft auch in konstantem Raum. Während Programmierer in eifrigen funktionalen Sprachen lernen, foldr aufgrund von Platz- und Terminierungsproblemen zu vermeiden, sind diese in faulen Sprachen nicht immer zutreffend!)

Dies hängt natürlich davon ab, dass Haskell wird faul bewertet, aber es sollte trotzdem möglich sein, dies in einer eifrigen Sprache wie Scala zu simulieren - ich weiß, dass es eine lazy val Funktion hat, die dafür geeignet sein könnte. Es sieht so aus, als müssten Sie eine lazyFold-Funktion schreiben, die nach rechts klappt, aber die Rekursion findet innerhalb eines Lazy-Wertes statt. Möglicherweise haben Sie jedoch weiterhin Probleme mit der Speicherplatznutzung.