Какой хороший способ переписать эту нерекурсивную функцию?

Ответ 1

Пожалуйста, не уменьшайте это, потому что это уродливо. Я знаю это уродливо. Но это способ сделать это в стиле батут (без переполнения системного стека) и без использования gotos.

push x,1 on homemade stack
while stack length > 1
  n = pop
  if (n==1)
    x = pop
    if (type(x)==NIL || type(x)==TEXT)
      push x // this is the "return value"
    else if (type(x)==CONCAT)
      push 2 // say call doc-concat
      push doc2(x), 1 // 2nd recursion
      push doc1(x), 1 // 1st recursion
    else if (type(x)==NEST)
      push 3 // say call doc-nest
      push level(x) // push level argument to doc-nest
      push doc(x), 1 // schedule recursion
    else if (type(x)==LINE)
      push " " // return a blank
    else if (type(x)==UNION)
      push doc1(x), 1 // just recur
  else if (n==2)
    push doc-concat(pop, pop) // finish the CONCAT case
  else if (n==3)
    push doc-nest(pop, pop) // finish the NEST case
  endif
endwhile
// final value is the only value on the stack

Ответ 2

Основное препятствие для простого преобразования вашего алгоритма заключается в том, что оно не приводит к последовательности вызовов одной и той же функции; но чередуется между несколькими, каждый из которых работает на результат другого.

Я бы сказал, что у вас есть три альтернативы:

• полностью переформулировать алгоритм (что делает примеры Фибоначчи).
  • объединить все функции в один, с большим количеством cond (уродливый, и, возможно, не приведет к реальной хвостовой рекурсии даже с одной функцией).
  • выверните поток изнутри: напишите единственную простую хвостовую рекурсивную функцию, которая преобразует входные данные в последовательность выполняемых операций и затем оценивает ее.

Ответ 3

Если сглаживание вызывает себя дважды (в случае: CONCAT), как его можно превратить в цикл? Может быть, я что-то упустил. Кажется, это по сути древовидная прогулка.

Я имею в виду, что есть способы сделать древовидную прогуровку без стека, но что-то должно быть неограниченным, например, если вы делаете это с помощью FIFO или, как было предложено, с продолжением.

Ответ 4

Вы можете использовать продолжение-прохождение:

(define (frob0 x k)
  (cond ((foo? x)
         (k x))
        ((bar? x)
         (frob0 (g x) 
           (lambda (y) 
             (k (macerate (f x) y))))
        ((thud? x)
         (frob0 (g x) 
           (lambda (y)
             (frob0 (h x) 
               (lambda (z)
                 (k (frobnicate y z))))))))

(define (frob x)
  (frob0 x (lambda (y) y))

Это не упростит понимание: - (

Ответ 5

Стандартная общая техника - это преобразование в батутный стиль. Для вашей конкретной проблемы (реализации симпатизирующих комбинаторов) вы можете найти полезную статью Derek Oppen 1980 "Допечатная подготовка" (не в Интернете AFAIK). Он представляет собой алгоритм, основанный на стеках, аналогичный более позднему функциональному алгоритму Wadler.

Ответ 6

Лучшее, что я могу придумать, это что-то вроде этого:

(define (doaction vars action)
  (cond ((symbol=? action 'frob)
         (cond ((foo? (first vars))
                (first vars))
               ((bar? (first vars))
                (doaction (list (f (first vars)) (doaction (g x) 'frob)) 'macerate)
etc...

Это не полностью хвост рекурсивный, но, вероятно, лучшее, что вы можете получить. ТШО - это действительно путь. (Я понимаю, что Clojure не может иметь этого из-за JVM).

Ответ 7

Ниже приведен не конкретный ответ на ваш вопрос, но, надеюсь, это будет полезный пример. Он заменяет несколько рекурсий (которые в противном случае нуждаются в неограниченном стеке вызовов) со стеком задач.

(в коде Haskellish):

data Tree = Null | Node Tree Val Tree

-- original, non-tail-recursive function: flatten :: Tree → Result flatten Null = nullval flatten (Node a v b) = nodefunc (flatten a) v (flatten b)

-- modified, tail-recursive code: data Task = A Val Tree | B Result Val

eval :: Tree → [Task] → Result use :: Result → [Task] → Result

eval Null tasks = use nullval tasks eval (Node a v b) tasks = eval a ((A v b):tasks)

use aval ((A v b):tasks) = eval b ((B aval v):tasks) use bval ((B aval v):tasks) = use (nodefunc aval v bval) tasks use val [] = val

-- actual substitute function flatten2 :: Tree → Result flatten2 tree = eval tree []