Что стандартный путь состоит в том, чтобы оптимизировать взаимную рекурсию в F#/Scala?
Эти языки не поддерживают оптимизацию взаимно рекурсивных функций 'исходно', таким образом, я предполагаю, что это должен быть батут или.. heh.. перезапись как цикл), я пропускаю что-то?
ОБНОВЛЕНИЕ: кажется, что я действительно лгал о Фа-диезе, но я просто не видел примера взаимных последних вызовов при поиске с помощью Google
3 ответа
Прежде всего, F# поддерживает взаимно рекурсивные функции нативно, поскольку может воспользоваться инструкцией tailcall, которая доступна в .NET IL (MSDN). Однако это немного сложно и может не работать в некоторых альтернативных реализациях .NET (например, Compact Frameworks), поэтому иногда вам придется решать эту проблему вручную.
В общем, есть несколько способов решения этой проблемы:
Trampoline - выбросить исключение, когда глубина рекурсии слишком велика, и реализовать цикл верхнего уровня, который обрабатывает исключение (исключение будет нести информацию для возобновления вызова). Вместо исключения можно также просто вернуть значение, указывающее, что функция должна быть вызвана снова.
Развертка с помощью таймера - когда глубина рекурсии слишком велика, вы создаете таймер и даете ему обратный вызов, который будет вызван таймером через некоторое очень короткое время (таймер продолжит рекурсию, но использованный стек будет сброшен).
То же самое можно сделать с помощью глобального стека, в котором хранится работа, которую нужно выполнить. Вместо того чтобы планировать таймер, вы бы добавили функцию в стек. На верхнем уровне программа будет выбирать функции из стека и выполнять их.
Чтобы привести конкретный пример первой техники, в F# можно написать следующее:
type Result<´T> =
| Done of ´T
| Call of (unit -> ´T)
let rec factorial acc n =
if n = 0 then Done acc
else Call(fun () -> factorial (acc * n) (n + 1))
Это можно использовать и для взаимно рекурсивных функций. Императивный цикл будет просто вызывать функцию f, хранящуюся в Call(f), пока не выдаст Done с конечным результатом. Я думаю, что это, вероятно, самый чистый способ реализовать это.
Я уверен, что есть и другие сложные методы решения этой проблемы, но это два, о которых я знаю (и которые я использовал).
В Scala 2.8, scala.util.control.TailCalls :
import scala.util.control.TailCalls._
def isEven(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty)
done(true)
else
tailcall(isOdd(xs.tail))
def isOdd(xs: List[Int]): TailRec[Boolean] = if (xs.isEmpty)
done(false)
else
tailcall(isEven(xs.tail))
isEven((1 to 100000).toList).result
Просто чтобы иметь код под рукой, когда вы будете бинговать за взаимную рекурсию в F#:
let rec isOdd x =
if x = 1 then true else isEven (x-1)
and isEven x =
if x = 0 then true else isOdd (x-1)
printfn "%A" (isEven 10000000)
Это вызовет StackOverflow, если вы компилируете без хвостовых вызовов (по умолчанию в режиме "Debug", который сохраняет стеки для более легкой отладки), но будет работать нормально, если компилировать с хвостовыми вызовами (по умолчанию в режиме "Release"). Компилятор выполняет вызовы хвостов по умолчанию (см. опцию --tailcalls), и реализации .NET на большинстве платформ поддерживают это.