Есть ли концепция "сгибать" или "найти с аккумулятором" в функциональном программировании?
Название говорит об этом, действительно; итерация по коллекции при сохранении состояния между циклами и завершающей итерации на основе условия завершения в дополнение к простому исчерпанию элементов может быть наиболее распространенной схемой для выполнения чего-либо в императивном программировании. Мне кажется, что это что-то функциональное, мягкопрограммируемое, соглашалось не говорить, или, по крайней мере, я никогда не сталкивался с его идиомой или полу-стандартизованным именем, например 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 s, но итераторы имели, возможно, меньшие накладные расходы, чем преобразование items в Stream, поскольку реализация по умолчанию для последнего использует итератор в любом случае).
Мои вопросы:
1) Имеет ли эта концепция название в функциональном программировании, и если да, то каков шаблон, связанный с его реализацией?
2) Что было бы лучшим (то есть кратким, общим, ленивым и с наименьшими издержками) способом реализовать его в scala?
Ответы
Ответ 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)
Ответ 2
Функциональный способ выполнения таких действий: Рекурсия хвоста:
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, чтобы принудительно скомпилировать компиляцию, если функция, которую вы аннотируете, не хвост рекурсивный. Я предлагаю вам использовать его как можно больше, потому что это помогает как избежать ошибок, так и документировать код.
Ответ 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, которая делает правильную складку, но рекурсия происходит в ленивом значении. Однако у вас могут быть проблемы с использованием пространства.
