0

私はSchemeを学んでおり、おもちゃの例として、Towers of Hanoiのソリューションベリファイア（ソルバーではない）を行っています。私は純粋に機能的なスタイルを使用したいと考えており (考え方を理解するためだけに)、タワーを 3 つのリストの単純なリストとして表しています。開始状態は次のようになります: '((0 1 2 3 4) () ())

状態、ソース インデックス、ターゲット インデックスを受け取り、新しい状態を返す関数を実装するにはどうすればよいですか? 命令型のスタイルでは、これは次のような簡単なものになります。

state[target].push(state[source].pop())

しかし、私が考えることができるすべての機能的な解決策は、ひどく複雑です. 例えば：

(define (makeMove state source target)
  (letrec ((recMake (lambda(tower pos disc)
              (if (null? tower) '()
              (cons (if (eqv? pos source)
                    (cdr (car tower))
                    (if (eqv? pos target) 
                    (cons disc (car tower))
                    (car tower)))
                (recMake (cdr tower)
                     (+ pos 1)
                     disc))))))
    (recMake state 0 (car (list-ref state source)))))

これはうまくいくようですが、もっと良い方法があるはずです。マップは再帰よりもいくらか優れていると思いますが、それでも多すぎます。状態を別の方法で表現した方が簡単でしょうか?

また、私のコードを自由に批判してください。私は自分が何をしているのかよくわかりません。

編集: 可能であれば、タワーの数が常に 3 であると想定しないでください。

4

1 に答える 1

1

これが超簡単な方法です。あなたの実装におけるディスクの「数字」の重要性はわかりませんが、あなたの答えと同じように動作させ、それらを押したりポップしたりしました。

(define (make-move state source target)
  (define (alter-tower tower index disc)
    (cond ((= index source) (cdr tower))       ; remove a disc
          ((= index target) (cons disc tower)) ; add a disc
          (else tower)))                       ; this tower wasn't changed
  (let ((disc (car (list-ref state source))))
    (let ((s0 (alter-tower (list-ref state 0) 0 disc))
          (s1 (alter-tower (list-ref state 1) 1 disc))
          (s2 (alter-tower (list-ref state 2) 2 disc)))
      (list s0 s1 s2))))

map-with-index多くの言語やライブラリで標準になっているが、Scheme には組み込まれていない関数が存在すると仮定すると、各タワーの操作の一番下のセットをその呼び出しにまとめることができ、はるかにクリーンになります。

一般に、必要なことを実行する、可能な限り低いレベルまでの純粋な関数を考え出すようにしてください。このソリューションでは、単一のタワーでコマンドの結果を返すことができる純粋な関数「alter-tower」を発明しました。これにより、ソリューションの残りの部分が非常に簡単になります。

あなたがフィードバックを求めたので、それが数値に適用された場合=と同じであることに注意してください。キャメルケースを使用する代わりに、ハイフンを使用した単語識別子。幸運を！eqv?defines

編集: たとえば、Racketのリスト内包表記を使用するバージョンは次のとおりです。

(define (make-move state source target)
  (define (alter-tower tower index disc)
    (cond ((= index source) (cdr tower))       ; remove a disc
          ((= index target) (cons disc tower)) ; add a disc
          (else tower)))                       ; this tower wasn't changed
  (let ((disc (car (list-ref state source))))
    (for/list ([(tower idx) (in-indexed state)])
      (alter-tower tower idx disc))))

多くの関数型言語にはmap、インデックスを消費する述語を取ることができる があるため、これらの 2 行は代わりに次のようになります。

(map (lambda (tower idx) (alter-tower tower idx disc)) state)

そのため、Scheme の方言とライブラリによっては異なる場合があります。(これに関する SRFI はないと思いますが、間違っているかもしれません。) または、常に上記のバージョンのmap自分自身を書くこともできます。

于 2011-09-28T16:08:05.337 に答える