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

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

12 голосов
/ 25 ноября 2008

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

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)))))

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

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

(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 явную функцию батута .

Ответы [ 7 ]

6 голосов
/ 25 ноября 2008

Пожалуйста, не отрицайте это, потому что это ужасно. Я знаю, это ужасно Но это способ сделать это в стиле батута (без переполнения системного стека) и без использования 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
3 голосов
/ 25 ноября 2008

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

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

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

Стандартный общий метод - преобразование в стиль батута . Для вашей конкретной задачи (реализация комбинаторов prettyprinting) вам может пригодиться статья Дерека Оппена 1980 года «Prettyprinting» (не в сети AFAIK). Он представляет собой основанный на стеке императивный алгоритм, аналогичный более позднему функциональному алгоритму Вадлера.

2 голосов
/ 25 ноября 2008

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

(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))

Это не облегчит понимание: - (

2 голосов
/ 25 ноября 2008

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

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

0 голосов
/ 26 ноября 2008

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

(в коде Haskellish): data Tree = Null | Node Tree Val Tree</p> <p>-- original, non-tail-recursive function: flatten :: Tree -> Result flatten Null = nullval flatten (Node a v b) = nodefunc (flatten a) v (flatten b)</p> <p>-- modified, tail-recursive code: data Task = A Val Tree | B Result Val</p> <p>eval :: Tree -> [Task] -> Result use :: Result -> [Task] -> Result</p> <p>eval Null tasks = use nullval tasks eval (Node a v b) tasks = eval a ((A v b):tasks)</p> <p>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</p> <p>-- actual substitute function flatten2 :: Tree -> Result flatten2 tree = eval tree []

0 голосов
/ 25 ноября 2008

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

(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).

...