Czy istnieje pojęcie "fold with break" lub "find with accumulator" w programowaniu funkcjonalnym?

Question

Tytuł mówi wszystko, naprawdę; Iterowanie nad zbieraniem, przy zachowaniu stanu między pętlami i kończącej iteracji w oparciu o warunek zakończenia, oprócz po prostu wyczerpania elementów może być najczęstszym wzorcem do wykonania czegokolwiek w imperatywnym programowaniu. Wydaje mi się jednak, jakby coś gentleprogrammers funkcjonalne zgodził się nie rozmawiać, a przynajmniej nigdy nie napotkał idiom dla niego lub semi-standaryzowanego nazwy takie jak z map, fold, reduce itp

często używam kod śledzenia w 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 
     } 

    } 

} 

Ale to jest brzydkie. Ilekroć próbuję bardziej deklaratywny podejście, przyjdę jeszcze dłuższy i prawie na pewno wolniejszego kodu, podobny do:

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 

(wariant bardziej funkcjonalne użyłby List s lub Stream s, ale iteratory mają zapewne mniejsze obciążenie niż konwersji items do Stream, jako domyślna implementacja dla tego ostatniego używa i tak pod iteratorem).

Moje pytania są następujące:

1) Czy pojęcie to ma nazwę w programowania funkcyjnego, a jeśli tak, to jaki jest wzór związany z jego realizacją?

2) Jaki byłby najlepszy (tj. Zwięzły, ogólny, leniwy i najmniejszy narzut) sposób wdrożenia go w scala?

Answer 1

ta jest mile widziana przez purystów Scala, ale można użyć return oświadczenie takiego:

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

Lub, jeśli jesteś jednym z tych, marszcząc brwi, a chcieliby czysto funkcjonalne rozwiązanie bez brudnych nadrzędnymi sztuczek można użyć coś leniwy, jak iterator lub strumienia:

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

Answer 2

Funkcjonalny sposób robienia takich rzeczy jest poprzez 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) 
    } 
} 

Korzystanie rekursji można zdecydować, na każdym kroku, jeśli chcesz kontynuować lub nie bez użycia break i bez narzutu, ponieważ ogon rekursji są konwertowane na iteracje z kompilatora.

Ponadto dopasowywanie do wzorca jest często używane do rozłożenia sekwencji. Na przykład, jeśli miał List można zrobić:

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 ma @scala.annotation.tailrec adnotacji do siła kompilacja się nie powiedzie, jeśli funkcja jesteś komentowania nie jest ogon rekurencyjne. Sugeruję, aby używać go tak często, jak to tylko możliwe, ponieważ pomaga to zarówno uniknąć błędów, jak i udokumentować kod.

Answer 3

prawo krotnie, po zakończeniu leniwie, można zrobić wcześniejszego zakończenia.W Haskell, na przykład, można napisać funkcję find (Return pierwszy element listy, która spełnia predykat) z 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) 

Co dzieje podczas próby, powiedzmy, find even [1..]? (Zauważ, że jest to lista nieskończona!)

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 

Lenistwo oznacza, że ​​funkcja, że ​​krotnie (\a r -> if even a then Just a else r) dostaje się zdecydować, czy zmusić r argumentów-taki, którego ocena wymaga od nas rekursja dół listy -w ogóle. Więc kiedy even 2 ocenia się na True, wybieramy gałąź if ... then ... else ..., która odrzuca wynik obliczony poza końcem listy - co oznacza, że ​​nigdy go nie oceniamy. (Działa również w stałej przestrzeni.) Podczas gdy programiści w gorliwych językach funkcjonalnych uczą się unikać foldr z powodu problemów z przestrzenią i zakończeniem, nie zawsze są one prawdziwe w leniwych językach!)

To oczywiście zależy od tego, że Haskell jest leniwie oceniany, ale mimo to powinno być możliwe symulowanie tego w gorliwym języku, takim jak Scala - wiem, że ma on funkcję lazy val, która może być użyta do tego. Wygląda na to, że musisz napisać funkcję lazyFold, która ma prawą fałdę, ale rekurencja ma miejsce w leniwej wartości. Jednak nadal możesz mieć problemy z wykorzystaniem przestrzeni.