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

По какой-то причине у меня возникают проблемы с хорошим выбором для перезаписи этой функции, поэтому она использует постоянное пространство стека. Большинство онлайн-дискуссий об обмане рекурсии деревьев используют функцию Фибоначчи и используют свойства этой конкретной проблемы. Есть ли у кого-нибудь идеи для этого "реального мира" (ну, более реального мира, чем серия Фибоначчи) использование рекурсии?

Clojure - интересный случай, поскольку он не имеет оптимизации хвостового вызова, а только хвостовую рекурсию через специальную форму "recur", Это также сильно препятствует использованию изменчивого состояния. У этого есть много ленивых конструкций, включая tree-seq, но я не могу понять, как они могут помочь мне в этом случае. Может ли кто-нибудь поделиться некоторыми методами, которые они выбрали из C, Scheme, Haskell или других языков программирования?

(defn flatten [x]
  (let [type (:type x)]
    (cond (or (= type :NIL) (= type :TEXT))
          x
          (= type :CONCAT)
          (doc-concat (flatten (:doc1 x))
                      (flatten (:doc2 x)))
          (= type :NEST)
          (doc-nest (:level x)
                    (flatten (:doc x)))
          (= type :LINE)
          (doc-text " ")
          (= type :UNION)
          (recur (:doc1 x)))))

edit: по запросу в комментариях...

Пересмотрено в общих чертах и с использованием Схемы - как я могу переписать следующий шаблон рекурсии, чтобы он не занимал пространство стека или не нуждался в оптимизации вызовов не-самих вызовов?

(define (frob x)
  (cond ((foo? x)
         x)
        ((bar? x)
         (macerate (f x) (frob (g x))))
        ((thud? x)
         (frobnicate (frob (g x))
                     (frob (h x))))))

Я выбрал раздражающие имена, чтобы отвезти домой, что я ищу ответы, которые не зависят от алгебраических свойств x, macerate, frobnicate, f, g или h. Я просто хочу переписать рекурсию.

UPDATE

Rich Hickey любезно добавил явную функцию батута до Clojure.

Ответ 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 []