Можно ли использовать продолжения, чтобы сделать tailRight рекурсивным?

Question

Следующая статья блога показывает, как в F # foldBack можно сделать хвостовую рекурсию, используя стиль передачи продолжения.

В Scala это будет означать, что:

def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
  l match {
    case x :: xs => f(x, foldBack(xs, acc)(f))
    case Nil => acc
  }
} 

можно сделать хвостовой рекурсивной, выполнив это:

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    l match {
      case x :: xs => loop(xs, (racc => k(f(x, racc))))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

К сожалению, я все еще получаю переполнение стека для длинных списков. Цикл является хвостовым рекурсивным и оптимизированным, но я думаю, что накопление стека просто перемещено в вызовы продолжения

Почему это не проблема с F #? И есть ли способ обойти это с помощью Scala?

Редактировать : здесь приведен код, показывающий глубину стека:

def showDepth(s: Any) {
  println(s.toString + ": " + (new Exception).getStackTrace.size)
}

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    showDepth("loop")
    l match {
      case x :: xs => loop(xs, (racc => { showDepth("k"); k(f(x, racc)) }))
      case Nil => k(acc)
    }
  }
  loop(list, u => u)
} 

foldCont(List.fill(10)(1), 0)(_ + _)

Это печатает:

loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
loop: 50
k: 51
k: 52
k: 53
k: 54
k: 55
k: 56
k: 57
k: 58
k: 59
k: 60
res2: Int = 10

Answer 1

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

def foldContTC[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  import scala.util.control.TailCalls._
  @annotation.tailrec
  def loop(l: List[T], k: (U) => TailRec[U]): TailRec[U] = {
    l match {
      case x :: xs => loop(xs, (racc => tailcall(k(f(x, racc)))))
      case Nil => k(acc)
    }
  }
  loop(list, u => done(u)).result
} 

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

val size = 1000
val list = List.fill(size)(1)
val warm = 10
val n = 1000
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldCont", warm, lots(n, foldCont(list, 0)(_ + _)))
bench("foldRight", warm, lots(n, list.foldRight(0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))

Время:

foldContTC: warming...
Elapsed: 0.094
foldCont: warming...
Elapsed: 0.060
foldRight: warming...
Elapsed: 0.160
foldLeft: warming...
Elapsed: 0.076
foldLeft.reverse: warming...
Elapsed: 0.155

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

Редактировать: Как следует из комментариев Джона, здесь приведены временные характеристики элементов 1M, которые подтверждают, что производительность снижаетсяс большими списками.Также я узнал, что реализация библиотеки List.foldLeft не переопределена, поэтому я рассчитал следующее:

def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  list match {
    case x :: xs => foldLeft2(xs, f(x, acc))(f)
    case Nil => acc
  }
} 

val size = 1000000
val list = List.fill(size)(1)
val warm = 10
val n = 2
bench("foldContTC", warm, lots(n, foldContTC(list, 0)(_ + _)))
bench("foldLeft", warm, lots(n, list.foldLeft(0)(_ + _)))
bench("foldLeft2", warm, lots(n, foldLeft2(list, 0)(_ + _)))
bench("foldLeft.reverse", warm, lots(n, list.reverse.foldLeft(0)(_ + _)))
bench("foldLeft2.reverse", warm, lots(n, foldLeft2(list.reverse, 0)(_ + _)))

выход:

foldContTC: warming...
Elapsed: 0.801
foldLeft: warming...
Elapsed: 0.156
foldLeft2: warming...
Elapsed: 0.054
foldLeft.reverse: warming...
Elapsed: 0.808
foldLeft2.reverse: warming...
Elapsed: 0.221

Так что foldLeft2.reverse является победителем...

Answer 2

Почему это не проблема с F #?

F # оптимизирует все хвостовые вызовы.

И есть ли способ обойти это с помощью Scala?

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

EDIT

Результаты вашего теста показывают, что батуты Scala на лот быстрее, чем в прошлый раз, когда я их тестировал. Также интересно добавить эквивалентные тесты, используя F # и для больших списков (потому что нет смысла делать CPS для маленьких списков!).

За 1000х в списке из 1000 элементов на моем нетбуке с процессором Intel Atom 1,65 ГГц N570 я получаю:

List.fold     0.022s
List.rev+fold 0.116s
List.foldBack 0.047s
foldContTC    0.334s

Для списка из 1 000 000 элементов я получаю:

List.fold     0.024s
List.rev+fold 0.188s
List.foldBack 0.054s
foldContTC    0.570s

Вас также могут заинтересовать старые обсуждения этого в списке caml в контексте замены функций нерекурсивного списка OCaml оптимизированными функциями хвостовой рекурсии.

Answer 3

Проблема в самой функции продолжения (racc => k(f(x, racc))). Он должен быть оптимизирован для работы всего бизнеса, но это не так.

Scala не может оптимизировать вызовы хвоста для произвольных вызовов хвоста, только для тех, которые могут преобразовываться в циклы (то есть, когда функция вызывает себя, а не какую-то другую функцию).

Answer 4

Я опоздал на этот вопрос, но я хотел показать, как вы можете написать хвостовой рекурсивный FoldRight без использования полного батута; путем накопления списка продолжений (вместо того, чтобы они вызывали друг друга, когда это сделано, что приводит к переполнению стека) и сворачивания над ними в конце, что-то вроде сохранения стека, но в куче:

object FoldRight {

  def apply[A, B](list: Seq[A])(init: B)(f: (A, B) => B): B = {
    @scala.annotation.tailrec
    def step(current: Seq[A], conts: List[B => B]): B = current match {
      case Seq(last) => conts.foldLeft(f(last, init)) { (acc, next) => next(acc) }
      case Seq(x, xs @ _*) => step(xs, { acc: B => f(x, acc) } +: conts)
      case Nil => init
    }
    step(list, Nil)
  }

}

Складка, которая происходит в конце, сама является хвостовой рекурсией. Попробуйте в ScalaFiddle

С точки зрения производительности, он работает немного хуже, чем версия с хвостовым вызовом.

[info] Benchmark            (length)  Mode  Cnt   Score    Error  Units
[info] FoldRight.conts           100  avgt   30   0.003 ±  0.001  ms/op
[info] FoldRight.conts         10000  avgt   30   0.197 ±  0.004  ms/op
[info] FoldRight.conts       1000000  avgt   30  77.292 ±  9.327  ms/op
[info] FoldRight.standard        100  avgt   30   0.002 ±  0.001  ms/op
[info] FoldRight.standard      10000  avgt   30   0.154 ±  0.036  ms/op
[info] FoldRight.standard    1000000  avgt   30  18.796 ±  0.551  ms/op
[info] FoldRight.tailCalls       100  avgt   30   0.002 ±  0.001  ms/op
[info] FoldRight.tailCalls     10000  avgt   30   0.176 ±  0.004  ms/op
[info] FoldRight.tailCalls   1000000  avgt   30  33.525 ±  1.041  ms/op