Использование продолжения для преобразования двоичной рекурсии в хвостовую рекурсию - PullRequest
Новая
       49

Использование продолжения для преобразования двоичной рекурсии в хвостовую рекурсию

4 голосов
/ 02 марта 2012

Читая книгу «Программирование на F #», я нашел пример кода на странице 195 следующим образом: 

type ContinuationStep<'a> =
  | Finished
  | Step of 'a * (unit -> ContinuationStep<'a>)

let iter f binTree =
  let rec linearize binTree cont =
    match binTree with
    | Empty -> cont()
    | Node(x, l, r) ->
      Step(x, (fun () -> linearize l (fun() -> linearize r cont)))

  let steps = linearize binTree (fun () -> Finished)

  let rec processSteps step =
    match step with
    | Finished -> ()
    | Step(x, getNext)
      -> f x
        processSteps (getNext())

  processSteps steps

При использовании продолжения двоичная рекурсия обхода двоичного файла была преобразована в хвостовую рекурсивную функцию processSteps. Мой вопрос заключается в том, что другая функция, linearize, кажется нерекурсивной. Означает ли это, что мы не можем полностью преобразовать двоичную рекурсию в хвостовую рекурсию, даже используя продолжение?

Ответы [ 2 ]

7 голосов
/ 02 марта 2012

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

fun () -> linearize l (fun() -> linearize r cont)

не звонит linearize. Вычисление приостанавливается до тех пор, пока processSteps не вызовет getNext ().

6 голосов
/ 02 марта 2012

Пример немного тонкий, потому что он не использует обычные продолжения, а вместо этого строит структуру, которая может быть оценена шаг за шагом. В месте, где вы обычно делаете рекурсивный вызов, он возвращает значение Step, которое содержит функцию, которую вы (рекурсивно) вызываете.

Во втором случае функция linearize возвращает Step, содержащую функцию, которая будет вызывать linearize рекурсивно, но она не немедленно делает рекурсивный вызов. Таким образом, функция не выполняет рекурсивный вызов (она просто сохраняет рекурсивную ссылку).

Имеет смысл рассмотреть вопрос о том, является ли программа хвостовой рекурсивной, когда вы смотрите на processSteps, потому что она выполняет реальный цикл - и это хвостовая рекурсивность, потому что она запускает Step на Step без сохранение стекового пространства для каждого Step.

Если вы хотите создать список вместо цепочки ленивых шагов, вам придется сделать рекурсивный вызов linearize непосредственно внутри продолжения: 

let rec linearize binTree cont = 
  match binTree with 
  | Empty -> cont [] 
  | Node(x, l, r) -> 
      linearize l (fun l -> linearize r (fun v -> cont (x::v)))

По сути, это то же самое, что и предыдущая функция, но на самом деле она вызывает linearize вместо построения Step, содержащей функцию, которая будет вызывать linearize.

...