Элегантный способ перевернуть список с помощью foldRight?

Question

Я читал о методах сгиба в книге Programming in Scala и наткнулся на этот фрагмент:

def reverseLeft[T](xs:List[T]) = (List[T]() /: xs) {
    (y,ys) => ys :: y
}

Как видите, это было сделано с помощью оператора foldLeft или /:. Любопытно, как бы это выглядело, если бы я делал это, используя :\, я придумал это:

def reverseRight[T](xs:List[T]) = (xs :\ List[T]()) {
    (y,ys) => ys ::: List(y)
}

Насколько я понимаю, ::: не такой быстрый, как ::, и имеет линейную стоимость в зависимости от размера списка операндов. По общему признанию, у меня нет опыта в CS и опыта работы в FP. Итак, мои вопросы:

• Как распознать / различить foldLeft / foldRight при проблемных подходах?
• Есть ли лучший способ сделать это без использования :::?

Answer 1

Поскольку foldRight на List в стандартной библиотеке строго и реализовано с использованием линейной рекурсии, вам следует избегать ее использования, как правило. Итеративная реализация foldRight будет выглядеть следующим образом:

def foldRight[A,B](f: (A, B) => B, z: B, xs: List[A]) =
  xs.reverse.foldLeft(z)((x, y) => f(y, x))

Рекурсивная реализация foldLeft может быть такой:

def foldLeft[A,B](f: (B, A) => B, z: B, xs: List[A]) =
  xs.reverse.foldRight(z)((x, y) => f(y, x))

Итак, вы видите, если оба строгие , то один или другой из foldRight и foldLeft будут реализованы (концептуально в любом случае) с reverse. Так как списки построены с :: связями справа, прямое итеративное сгиб будет foldLeft, а foldRight просто "наоборот, затем foldLeft".

Интуитивно, вы можете подумать, что это будет медленная реализация foldRight, поскольку она сворачивает список дважды. Но:

1. «Дважды» в любом случае является постоянным фактором, поэтому он асимптотически эквивалентен фолду один раз.
2. В любом случае, вам придется дважды просмотреть список. Один раз поместить вычисления в стек, а затем снова выбросить их из стека.
3. Реализация foldRight выше быстрее, чем в стандартной библиотеке.

Answer 2

Операции над списком намеренно не симметричны.Структура данных List представляет собой односвязный список, в котором каждый узел (и данные, и указатель) являются неизменяемыми.Идея, лежащая в основе этой структуры данных, заключается в том, что вы выполняете изменения в начале списка, беря ссылки на внутренние узлы и добавляя новые узлы, которые указывают на них - разные версии списка будут использовать одни и те же узлы для конца списка.

Оператор :::, который добавляет новый элемент в конец списка, должен создать новую копию всего списка, потому что в противном случае он изменил бы другие списки, которые совместно используют узлы со списком, в котором вы находитесь.добавление к.Вот почему ::: занимает линейное время.Scala имеет структуру данных, называемую ListBuffer, которую вы можете использовать вместо оператора :::, чтобы ускорить добавление в конец списка.По сути, вы создаете новый ListBuffer, и он начинается с пустого списка.ListBuffer поддерживает список полностью отдельный от любого другого списка, о котором знает программа, поэтому его можно безопасно изменить, добавив в конец.Когда вы закончите добавление в конец, вы вызываете ListBuffer.toList, который выпускает список в мир, после чего вы больше не можете добавлять в конец, не копируя его.

foldLeftи foldRight также имеют сходную асимметрию.foldRight требует, чтобы вы прошли по всему списку, чтобы добраться до конца списка, и отслеживали все места, которые вы посетили на пути туда, чтобы вы посетили их в обратном порядке.Обычно это делается рекурсивно и может привести к foldRight переполнению стека в больших списках.foldLeft, с другой стороны, имеет дело с узлами в порядке их появления в списке, поэтому он может забыть те, которые он уже посещал, и ему нужно знать только об одном узле за раз.Хотя foldLeft также обычно реализуется рекурсивно, он может воспользоваться оптимизацией под названием исключение хвостовой рекурсии , в которой компилятор преобразует рекурсивные вызовы в цикл, потому что функция ничего не делает после возврата изрекурсивный вызов.Таким образом, foldLeft не переполняет стек даже в очень длинных списках. EDIT : foldRight в Scala 2.8 на самом деле реализовано путем обращения к списку и запуска foldLeft в обратном списке - поэтому проблема хвостовой рекурсии не является проблемой - обе структуры данных правильно оптимизируют хвостовую рекурсию, и вы можете выбрать любой из них (вы попадаете в проблему сейчас, когда определяете reverse в терминах reverse - вам не нужно беспокоиться, если вы определяете свой собственный Обратный метод для удовольствия, но у вас не было бы опции foldRight, если бы вы определяли обратный метод Scala.)

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

(В алгоритме, который будет объединять foldLeft с ::: или foldRight с ::, вам необходимо принять решение для себя, что является более важным:место в стеке или время выполнения. Или вы должны использовать foldLeft с ListBuffer.)