Есть ли концепция «сбрасывать с перерывом» или «найти с аккумулятором» в функциональном программировании?

Question

Заглавие гласит все, действительно; итерация по коллекции при сохранении состояния между циклами и завершающей итерации на основе условия завершения в дополнение к простому исчерпанию элементов может быть наиболее распространенной схемой для выполнения чего-либо в императивном программировании. Мне кажется, однако, как это что-то функциональные gentleprogrammers договорились не говорить об этом, или по крайней мере, я никогда не сталкивался с идиомы для него или полу-стандартизировано именем, например, как с map, fold, reduce и т.д.

Я часто использую последующий код в 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 
     } 

    } 

} 

Но это уродливо. Всякий раз, когда я пытаюсь более декларативный подход, я прихожу с еще дольше и почти наверняка более медленным кодом, сродни:

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 

(Более функциональный вариант будет использовать List с или Stream с, но итераторы имеют, возможно, меньшую нагрузку, чем преобразование items - Stream, так как для реализации по умолчанию для последнего используется итератор в любом случае).

Мои вопросы:

1) Имеет ли это понятие имя в функциональном программировании, и если да, то это шаблон, связанный с его реализацией?

2) Что было бы лучшим (то есть кратким, общим, ленивым и с наименьшим издержком) способом реализовать его в scala?

Answer 1

Это неодобрение SCALA пуристов, но вы можете использовать return подобное заявление:

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

Или, если вы один из тех, нахмурившись, и хотел бы чисто функциональное решение без грязных императивных трюков , вы можете использовать что-то ленивым, как итератор или поток:

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

Answer 2

Функциональный способ делать такие вещи через 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) 
    } 
} 

Использование рекурсии вы можете решить на каждый шаг, если вы хотите продолжить или не без использования break и без каких-либо накладных расходов, потому что хвоста рекурсий преобразуются в итерации из компилятора.

Кроме того, сопоставление образцов часто используется для разложения последовательностей. Например, если у вас List вы могли бы сделать:

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 имеет @scala.annotation.tailrec аннотацию к силе компиляции потерпеть неудачу, если функция вы аннотирование не хвоста рекурсивных. Я предлагаю вам использовать его как можно больше, потому что это помогает как избежать ошибок, так и документировать код.

Answer 3

Права раз, когда сделан лениво, можно сделать досрочное прекращение.В Haskell, например, вы можете написать find функции (вернуть первый элемент списка, который удовлетворяет предикат) с 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) 

Что происходит, когда вы пытаетесь, скажем, find even [1..]? (Обратите внимание, что это бесконечный список!)

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 

Лень означает, что функция, которую мы сложите с (\a r -> if even a then Just a else r) решает, следует ли заставить r аргумент-тот, чья оценка требует от нас рекурсивного списка вниз -вообще. Поэтому, когда even 2 оценивает True, мы выбираем ветку if ... then ... else ..., которая отбрасывает результат, вычисленный за хвостом списка, что означает, что мы никогда его не оцениваем. (Он также работает и в постоянном пространстве. Хотя программисты в нетерпеливых функциональных языках учатся избегать foldr из-за проблем с пространством и прекращением, это не всегда верно на ленивых языках!)

Это, конечно, зависит от того, что Haskell лениво оценивается, но, тем не менее, можно смоделировать это на страстном языке, таком как Scala. Я знаю, что у него есть функция lazy val, которая может быть использована для этого. Похоже, вам нужно написать функцию lazyFold, которая делает правильную складку, но рекурсия происходит в ленивом значении. Тем не менее, у вас могут быть проблемы с использованием пространства.