9

Clojureを学ぶために、 4clojureで問題を解いています。私は現在、 DFAが受け入れる言語 (の一部) を列挙する質問164について歯を磨いています。興味深い条件は、言語が無限である可能性があるため、ソリューションが遅延する必要があることです (その場合、ソリューションのテスト ケース.(take 2000 ...

私のマシンで機能するソリューションがありますが、それを Web サイトに送信すると、スタックが吹き飛ばされます (決定される許容文字列の量を 2000 から 20000 に増やすと、スタックもローカルで吹き飛ばされるため、私の解決策の欠陥）。

私の解決策[1]は次のとおりです。

(fn [dfa]
  (let [start-state (dfa :start)
        accept-states (dfa :accepts)
        transitions (dfa :transitions)]
    (letfn [
      (accept-state? [state] (contains? accept-states state))

      (follow-transitions-from [state prefix]
          (lazy-seq (mapcat 
            (fn [pair] (enumerate-language (val pair) (str prefix (key pair))))
            (transitions state))))

      (enumerate-language [state prefix]
        (if (accept-state? state) 
          (cons prefix (follow-transitions-from state prefix))
          (follow-transitions-from state prefix)))
      ]   
      (enumerate-language start-state ""))
  )
)

DFA を受け入れる

'{:states #{q0 q1 q2 q3}
              :alphabet #{a b c}
              :start q0
              :accepts #{q1 q2 q3}
              :transitions {q0 {a q1}
                            q1 {b q2}
                            q2 {c q3}}}

DFA が受け入れる言語を返します ( #{a ab abc})。ただし、DFA の最初の 2000 の受け入れられた文字列を決定するとき

(take 2000 (f '{:states #{q0 q1} 
                           :alphabet #{0 1}
                           :start q0
                           :accepts #{q0}
                           :transitions {q0 {0 q0, 1 q1} 
                                         q1 {0 q1, 1 q0}}}))

それはスタックを吹き飛ばします。明らかに、ソリューションを末尾再帰的に再構築する必要がありますが、それがどのように可能かわかりません。特に、遅延性と末尾再帰性を組み合わせることがどのように可能かさえわかりません ( または のいずれrecurかを介してtrampoline)。このlazy-seq関数はクロージャを作成するため、recurinsidelazy-seqを使用するとクロージャが再帰ポイントとして使用されます。lazy-seqinsideを使用する場合、引数を評価する必要がある関数呼び出しを発行するためrecur、lazy-seqは常に評価されます。recur

を使用する場合trampoline、要素を遅延評価できるリストを繰り返し作成する方法がわかりません。私がそれを使用して使用したのを見ると、trampoline最終的に終了したときにのみ値を返すことができます (つまり、トランポリン関数の 1 つが関数を返さない)。

他のソリューションは範囲外と見なされます

この質問の範囲外で、この 4Clojure の問題に対する別の種類の解決策を考えています。私は現在、を使用してソリューションに取り組んでいますiterate。各ステップは、「次のステップ」(現在の状態からの遷移に続く) が受け入れる文字列のみを計算するため、再帰はまったくありません。次に、現在の状態と、その状態になった文字列 (次の状態のプレフィックス) のみを追跡します。この場合、難しいのは、有限言語を受け入れる DFA が結果を返さなくなる時期を検出することです。take-while周囲の適切な停止基準をまだ考案していませんiterate、しかし、私はこのソリューションをうまく機能させることができると確信しています。この質問では、基本的な質問に興味があります: 怠惰と末尾再帰を組み合わせることができるか、それとも基本的に不可能ですか?

def[1]とを使用できないなど、サイトにはいくつかの制限があることに注意してくださいdefn。

4

2 に答える 2

7

を使用lazy-seqする代わりに、通常の関数呼び出しを使用するだけrecurです。怠惰は、他のrecur方法で使用される再帰的なスタック消費を回避します。

たとえば、次の簡略版repeat:

(defn 繰り返し [x]
  (lazy-seq (cons x (repeat x))))
于 2012-07-16T01:14:23.507 に答える
2

問題は、次のようなものを構築していることです。

(mapcat f (mapcat f (mapcat f ...)))

原則としてはこれで問題ありませんが、このリストの右端にある要素は長い間実現されず、実現するまでに、順番に強制する必要がある遅延シーケンスの膨大なスタックがあります。単一の要素を取得します。

ネタバレを気にしない場合は、https://gist.github.com/3124087で私のソリューションを確認できます。私はあなたとは異なる 2 つのことを行っていますが、どちらも重要です。

  1. 幅優先でツリーをトラバースします。それが受け入れられない状態である場合、q0 から q0 へのループで「立ち往生」したくありません。遷移が渡される順序のために失敗している特定のテスト ケースでは問題ないように見えますが、この後の次のテスト ケースにはその特徴があります。
  2. doall私が怠惰に構築しているシーケンスを強制するために使用します。多くconcatの s が非常に大きなスタックを構築し、シーケンスが無限にならないこともわかっているため、スタック オーバーフローを引き起こす遅延シーケンスの階層化を防ぐために、構築するときにすべてを強制します。

編集: 一般に、遅延シーケンスと末尾再帰を組み合わせることはできません。おそらく、単一の要素を追加する前に行うべき作業がさらにある場合は再実行し、新しい要素がある場合は遅延再帰しますが、ほとんどの場合、それらは反対の目標を持ち、結合しようとします。それらは不用意に痛みをもたらすだけで、特に改善はありません。

于 2012-07-16T18:16:44.953 に答える