FoldLeft v. foldRight - это важно?

Ранее Николас Ринаудо ответил на мой вопрос о Scala Список foldRight Always Using foldLeft?

Изучая Haskell в настоящее время, я понимаю, что foldRight должен быть предпочтительнее foldLeft в случаях, когда :: (preend) можно использовать над ++ (append).

Причиной, как я понимаю, является производительность - первое происходит в O(1), т.е. добавляет элемент к фронту - постоянное время. В то время как для последнего требуется O(N), т.е. Пройти весь список и добавить элемент.

В Scala, учитывая, что foldLeft реализуется в терминах foldRight, имеет ли значение использование :+ над ++ с foldRight значение, поскольку foldRight обращается вспять, а затем foldLeft'd?

В качестве примера рассмотрим эту простую операцию fold.. для простого возврата элементов списка в порядок.

foldLeft складывается над каждым элементом, добавляя каждый элемент в список через :+.

scala> List("foo", "bar").foldLeft(List[String]()) { 
                                                    (acc, elem) => acc :+ elem }
res9: List[String] = List(foo, bar)

foldRight выполняет операцию foldLeft с оператором :: для каждого элемента, но затем меняет направление.

scala> List("foo", "bar").foldRight(List[String]()) { 
                                                    (elem, acc) => elem :: acc }
res10: List[String] = List(foo, bar)

В действительности, имеет значение в Scala, который используется foldLeft или foldRight, учитывая, что foldRight использует foldRight?

Ответы

Ответ 1

Ответ @Rein Henrichs действительно не имеет отношения к Scala, потому что Scala реализация foldLeft и foldRight полностью отличается (для стартеров Scala имеет нетерпеливую оценку).

foldLeft и foldRight сами по себе очень мало что делают для выполнения вашей программы. Оба являются (либерально говоря) O (n * c_f), где c_f - сложность одного вызова функции f, которая задана. foldRight медленнее на постоянный коэффициент из-за дополнительного reverse.

Таким образом, реальный фактор, который отличает один от другого, - это сложность анонимной функции, которую вы даете. Иногда проще написать эффективную функцию, предназначенную для работы с foldLeft, а иногда и с foldRight. В вашем примере лучше использовать версию foldRight, так как анонимная функция, которую вы даете foldRight, равна O (1). Напротив, анонимная функция, которую вы даете foldLeft, сама O (n) (амортизируется, что здесь важно), потому что acc продолжает расти от 0 до n-1 и добавляет к списку n элементов O (n).

Поэтому на самом деле важно выбрать foldLeft или foldRight, но не из-за самих этих функций, а из-за анонимных функций, данных им. Если оба эквивалентны, выберите foldLeft по умолчанию.

Ответ 2

Я могу дать ответ для Haskell, но я сомневаюсь, что это будет иметь отношение к Scala:

Начните с источника для обоих,

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

Теперь посмотрим, где с правой стороны появляется рекурсивный вызов foldl или foldr. Для foldl он является внешним. Для foldr он находится внутри приложения f. Это имеет несколько важных последствий:

  • Если f - конструктор данных, этот конструктор данных будет самым левым, самым внешним с foldr. Это означает, что foldr реализует охраняемую рекурсию, так что возможно следующее:

    > take 5 . foldr (:) [] $ [1..]
[1,2,3,4]

    Это означает, что, например, foldr может быть как хорошим производителем, так и хорошим потребителем для коротких фьюжн. (Да, foldr (:) [] - тождественный морфизм для списков.)

    Это невозможно с помощью foldl, потому что конструктор будет внутри рекурсивного вызова foldl и не может быть сопоставлен с образцом.

  • И наоборот, поскольку рекурсивный вызов foldl находится в самом левом, крайнем положении, он будет уменьшаться ленивой оценкой и не займет места в стеке совпадения шаблонов. В сочетании с соответствующей аннотацией строгости (например, foldl') это позволяет выполнять функции, такие как sum или length, в постоянном пространстве.

Подробнее об этом см. в ленивой оценке Haskell.

Ответ 3

На самом деле имеет значение, используете ли вы foldLeft или foldRight в Scala, по крайней мере, в списках, по крайней мере, в реализации по умолчанию. Я считаю, что этот ответ не относится к библиотекам, таким как скалаз.

Если вы посмотрите на исходный код foldLeft и foldRight для LinearSeqOptimized, вы увидите, что:

  • foldLeft реализуется с помощью циклических и локальных изменяемых переменных и помещается в один стек кадров.
  • foldRight рекурсивный, но не хвостовой рекурсивный и, следовательно, потребляет один стек стека за элемент в списке.

foldLeft, таким образом, безопасен, а foldRight может переполнять переполнение для длинных списков.

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

Чтобы воспользоваться вашим примером, я считаю, что оптимальным решением является использование foldLeft, добавление результатов к вашему аккумулятору и reverse результат.

Таким образом:

  • вся операция O (n)
  • он не будет переполнять стек, независимо от размера списка

Это, по сути, то, что, по вашему мнению, вы делали с foldRight, если предположить, что он был реализован в терминах foldLeft.

Если вы используете foldRight, вы получите немного более быструю реализацию (ну, немного... в два раза быстрее, на самом деле, но все же O (n)) за счет безопасности.

Можно утверждать, что если вы знаете, что ваши списки будут достаточно маленькими, нет проблем с безопасностью, и вы можете использовать foldRight. Я чувствую, но это только мнение, что если ваши списки достаточно малы, что вам не нужно беспокоиться о вашем стеке, они достаточно малы, чтобы вам не приходилось беспокоиться о производительности.

Ответ 4

От этого зависит:

scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> l.foldLeft(List.empty[Int]) { (acc, ele) => ele :: acc }
res0: List[Int] = List(3, 2, 1)

scala> l.foldRight(List.empty[Int]) { (ele, acc) => ele :: acc }
res1: List[Int] = List(1, 2, 3)

Как вы можете видеть, foldLeft перемещает список из head в последний элемент. foldRight, с другой стороны, пересекает его от последнего элемента до head.

Если вы используете фальцовку для агрегирования, не должно быть разницы:

scala> l.foldLeft(0) { (acc, ele) => ele + acc }
res2: Int = 6

scala> l.foldRight(0) { (ele, acc) => ele + acc }
res3: Int = 6

Ответ 5

Я не эксперт Scala, но в Haskell одна из самых важных отличительных черт между foldl' (которая действительно должна быть левой клавишей по умолчанию) и foldr заключается в том, что foldr будет работать на бесконечном структуры данных, где foldl' будет вешать бесконечно.

Чтобы понять, почему это так, я рекомендую посетить foldl.com и foldr.com, несколько раз расширяя оценки и восстанавливая дерево вызовов. Вы быстро увидите, где foldr соответствует сравнению с foldl'.