4

私は現在、スキームセマンティクスを使用してPythonプログラムを作成しようとしているため、後で多くのPythonicに依存することなくSchemeに変換できます。

*、深さ優先、幅優先の検索アルゴリズムを使用して、スライド パズル問題 (正方形に配置された 9 つのスロットと 8 つのタイルがある) を解こうとしています。私は 11 年前に Lisp の AI クラスでこれを行いましたが、基本的に当時は Lisp について何も知らず、心から嫌いでした。振り返ってみると、Lisp で「C」をプログラミングしていたことに気づきました。教授はこの問題で助けにはなりませんでした。

2 つのタイルを簡単に交換できる Python 関数があります。 

def swap(p, (r1, c1), (r2, c2)):  
    # Swaps *any* two locations and returns new configuration  
    # Does not concern itself with zero location, etc  
    # Not sure how to do this functionally  
    p_p = p[:]  
    temp = p_p[r1][c1]  
    p_p[r1][c1] = p_p[r2][c2]  
    p_p[r2][c2] = temp  
    return p_p

これを SICP で見られるようなものに変えて、副作用などを回避したいと思います。

しかし、これは疑問を引き起こします。私が SICP で読んだものはすべて、再帰によるループです。一定時間で配列/ベクトル/リストにアクセスする際に何も見ませんでした。要素を読み取るためのループ的/再帰的な方法を想像することはできますが、set! のようなものを生成する副作用を呼び出さずに、クレイジーな if に頼ることなく、特定の要素を変更した新しいリストを作成する方法を想像するのは難しいと思います。どの要素を変更する必要があるかに関する /then/else 句。もちろん、2次元配列を考えると、これはさらに混乱します。この場合、多次元配列がネイティブにサポートされているため、Python を使用したソリューションは明らかです。

C/C++/Python/Matlab/Lua/その他では、[i] 構文を介してリスト/配列にアクセスするのは簡単で、その下のどこかでハードウェア指向のポインター ルックアップに直接変換されます。SICP バージョンの scheme で定義されたアトミック操作を考えると、scheme がこれを行う方法がわかりません。これらはすべて非常にループと検索指向のようです。ベクトルおよびリスト配列アクセス関数はどのように機能して一定時間のアクセスを取得しますか? （私はここではまったくの初心者なので、どの機能について話しているのかわかりません）。密かにアクセスされている C またはアセンブリ ライブラリはどこかにありますか? リスト/配列/ベクトルアクセスに使用できるスキームに固有の定数時間セマンティクスはありますか?

Schemishセマンティクスを使用してPythonで上記の関数を書き直すにはどうすればよいですか? 上記の関数をSchemeでどのように書き換えますか?

4

4 に答える 4

4

あなたの最初の問題は Lisp で C のセマンティクスを書こうとしていたことでした。Python でスキームのセマンティクスを書こうとして失敗を繰り返していませんか? 私は常に、言語 X を言語と同じくらいパラダイムとして学び、最も X っぽい方法で書くようにしています。

これが移行されることがわかっている業務アプリであれば妥当かもしれませんが、それ以外の場合は、最初からスキームで記述します。

于 2008-12-07T03:25:05.843 に答える
2

私は約 1 年前に Lisp で 8 パズル ソルバーを書きました。3 つのリストのリストを使用しました。各サブリストは 3 つの要素が数字です。一定時間ではありませんが、ポータブルです。

とにかく、これを機能的に行うことに本当に興味がある場合 (Scheme では必要ありません)、row/col を指定して特定の値を取得し、row/col を指定して値を「設定」するヘルパー関数を作成するのが最も簡単です。列。元のデータ構造を変更する代わりに、set 操作は古い状態に基づいて新しい状態を構築します。

次に、これらの get 操作と set 操作に基づいて swap 操作を記述できます。以下は、Common Lisp で約 1 年前に書いたものですが、Scheme に簡単に変換できます。

; getval
;
; This function takes a position (r . c) where and returns the corresponding
; number in the 8-puzzle state. For example, if you wanted (1 . 2) from
; ((1 2 3) (4 5 6) (7 8 9)), the value would be 6. The r and c values begin
; at 0.
;
; parameters:  pos    The position to get
;              state  The 8-puzzle state
; returns:     The value at pos in state
(defun getval (pos state)
  (if (null state) 'no-value
      (if (= 0 (car pos))
      (if (= 0 (cdr pos))
          (caar state)
          (getval (cons (car pos) (- (cdr pos) 1)) (list (cdar state))))
      (getval (cons (- (car pos) 1) (cdr pos)) (cdr state)))))

; setval
;
; This function returns a state where the value at pos is replaced by val.
; Like getval, this function is zero-based. Accessing beyond the size of
; the state is undefined (and probably broken)
;
; parameters:  pos    Position to set
;              val    Value to set
;              state  State to modify
; returns:     New state where pos is val
(defun setval (pos val state)
  (if (null state) '()
      (if (= 0 (car pos))
      (if (= 0 (cdr pos))
          (cons (cons val (cdar state)) (cdr state))
          (let ((temp (setval (cons (car pos) (- (cdr pos) 1)) val
                  (cons (cdar state) (cdr state)))))
        (cons (cons (caar state) (car temp)) (cdr temp))))
      (cons (car state) (setval (cons (- (car pos) 1) (cdr pos)) val (cdr state))))))

; state-swap
;
; This function takes a state and two positions and returns a new state with
; the values in those two positions swapped.
;
; parameters:  state  State to swap within
;              a      Position to swap with b
;              b      Position to swap with a
; return:      State with a swapped with b
(defun state-swap (state a b)
  (let ((olda (getval a state)) (oldb (getval b state)))
    (setval a oldb (setval b olda state))))
于 2008-12-07T00:56:32.760 に答える
1

これを達成するための 1 つの方法を次に示します。適切なマッピングを適用する関数を使用してリストを再作成します。

def swap(p, (r1,c1), (r2,c2)):
    def getitem(r,c):
        if (r,c) == (r1,c1): return p[r2][c2]
        elif (r,c) == (r2,c2): return p[r1][c1]
        return p[r][c]
    return [ [getitem(r,c) for c in range(len(p[0]))] for r in range(len(p)) ]

これをさらに一歩進めて、関数を実際のインターフェイスにすることもできます。この場合、各スワップは、以下の関数に渡す前に適切な変換を行う関数を返すだけです。特にパフォーマンスが高いわけではありませんが、厄介な可変データ構造を省くかなり単純な機能的アプローチです。

def swap(f, (r1,c1), (r2,c2)):
    def getitem(r,c):
        if (r,c) == (r1,c1): return f(r2,c2)
        elif (r,c) == (r2,c2): return f(r1,c1)
        return f(r,c)
   return getitem

l=[ [1,2,3], [4,5,6], [7,8,0]]
f=lambda r,c: l[r][c]    # Initial accessor function
f=swap(f, (2,1), (2,2))  # 8 right
f=swap(f, (1,1), (2,1))  # 5 down
print [[f(x,y) for y in range(3)] for x in range(3)]
# Gives: [[1, 2, 3], [4, 0, 6], [7, 5, 8]]
于 2008-12-07T23:59:49.673 に答える
0

いいね、lisp コードをありがとう。確実に取得できるように勉強する必要があります。

最初の答えは、私が初めて Lisp で「c を書いた」ときでした。なぜなら、それが私がプログラミング方法を知っていた唯一の方法であり、なぜ誰かが Lisp を使うのか見当もつかなかったからです。今回は、スキームをいじっていましたが、python を使いたかったので、何かに行き詰まった場合は、「チート」して pythonish を使用し、usenet の回答を待っている間に問題の次の部分に進みます。 .

于 2008-12-07T07:40:26.610 に答える