12

どういうわけか、この関数を一定のスタックスペースを使用するように書き直す良い方法を考えるのに苦労しています。フィボナッチ関数を使用し、その特定の問題の特性を利用することにより、ツリー再帰のチートに関するほとんどのオンラインディスカッションが行われます。この「現実世界」（フィボナッチ数列よりも現実世界）での再帰の使用について何かアイデアはありますか？

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

編集：コメントでリクエストして...

一般的な用語で言い換えると、Schemeを使用します-スタックスペースを消費したり、非自己呼び出しの末尾呼び出しの最適化を必要としないように、次の再帰パターンを書き直すにはどうすればよいですか？

(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の代数的特性に依存しない答えを探しているという点を理解するために、迷惑な名前を選びました。再帰を書き直したいだけです。

更新：

Rich Hickeyは、Clojureに明示的なトランポリン機能を追加してくれました。

4

7 に答える 7

6

醜いので、これに反対票を投じないでください。私はそれが醜いことを知っています。しかし、これはトランポリン スタイル (システム スタック オーバーフローなし) で、goto を使用せずに実行する方法です。

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
于 2008-11-25T00:32:43.403 に答える
3

アルゴリズムを簡単に変換する上での主な障害は、同じ関数の呼び出しが連続しないことです。しかし、いくつかのものの間で交互に行われ、それぞれが他の結果に作用します。

3つの選択肢があると思います：

  1. アルゴリズムを完全に再構築します (それがフィボナッチの例で行われていることです)。
    • すべての関数を 1 つの関数に結合して、多数の cond を使用します (醜く、単一の関数であっても、実際の末尾再帰にはならない可能性があります)。
    • フローを裏返しにします。入力データを実行する必要がある一連の操作に変換する単一の単純な末尾再帰関数を記述し、それを評価します。
于 2008-11-24T22:10:51.320 に答える
2

標準的な一般的なテクニックは、トランポリン スタイルへの変換です。特定の問題 (prettyprinting コンビネータの実装) については、Derek Oppen の 1980 年の論文「Prettyprinting」が参考になるかもしれません (Web の知る限りではありません)。これは、Wadler の後の機能的なアルゴリズムに似た、スタックベースの命令型アルゴリズムを提示します。

于 2008-11-25T00:34:26.583 に答える
2

flatten が自分自身を 2 回呼び出した場合 (:CONCAT の場合)、どのようにループに変えることができますか? 多分私は何かが足りない。それは本質的に木の散歩のようです。

つまり、スタックなしでツリー ウォークを実行する方法はありますが、FIFO を使用する場合や、提案されたように継続を使用する場合のように、何かを無制限にする必要があります。

于 2008-11-24T22:53:18.330 に答える
2

継続渡しを使用できます：

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

これは物事を理解しやすくするものではありません:-(

于 2008-11-24T23:29:31.067 に答える
0

私が思いつくことができる最高のものは次のようなものです：

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

完全に末尾再帰ではありませんが、おそらく最高のものを得ることができます。TCOは本当に行く方法です。（JVMが原因でClojureがそれを使用できないことを理解しています）。

于 2008-11-25T00:06:50.977 に答える
0

以下はあなたの質問に対する具体的な回答ではありませんが、役に立つ例になることを願っています。複数の再帰 (それ以外の場合は無制限の呼び出しスタックが必要になります) をタスクのスタックに置き換えます。

(Haskelish コードで): 

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 []

于 2008-11-26T00:32:06.680 に答える