4

I currently am trying to write a Python program using scheme semantics so I can later translate it into Scheme without relying on a lot of Pythonic stuff.

I'm trying solve the sliding puzzle problem (where you have 9 slots and 8 tiles arranged in a square) using a*, depth first, and breadth first search algorithm. I did this ~11 years ago in some AI class in Lisp, but basically at the time I had no idea about lisp, I hated it with all my heart, and only in retrospect do I realize I was programming "C" in Lisp. The prof didn't help in this matter.

I have a python function which can swap two tiles easily: 

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

I'd like to turn this into something you might find in SICP, avoiding side effects, etc.

But this brings up a question. Everything I read in SICP is loops via recursion. I didn't see anything in accessing arrays/vectors/lists in constant time. I can imagine a loopish/recursive way to read an element, but I find it harder to imagine a way to create a new list with a certain element changed, without invoking side-effect producing things like set!, and without resorting to crazy if/then/else clauses concerning which element should be changed. This of course gets more confusing when considering a 2d array. In this case the solution with python is obvious because of its native support for multidimensional arrays.

In C/C++/Python/Matlab/Lua/anything else, accessing lists/arrays via the [i] syntax is easy, and directly translates to a hardware-oriented pointer lookup somewhere underneath. I don't understand how scheme does this, given the atomic operations defined in the SICP version of scheme, which all seem very loop-and-search oriented. How do the vector and list array access functions work to get constant time access? (I'm a total newbie here, so I'm not ever sure what functions I'd be talking about). Is there a C or Assembly library someplace which is secretly being accessed? Are there any inherent constant-time semantics in scheme which could be used for list/array/vector access, and which would allow me a guilt-free way of using that idiom in Python for the moment?

How would can I rewrite the above function in python using Schemish semantics? How would I rewrite the above function in Scheme?

4

4 回答 4

4

您发现您最初的问题是尝试在 Lisp 中编写 C 语义。尝试在python中编写方案语义不是在重复错误吗？我总是尝试将语言 X 作为一种范式来学习，就像一种语言一样，并以最 X-ish 的方式写作。

如果这是您知道将要迁移的业务应用程序，这可能是合理的，但否则我只会在计划中编写它。

于 2008-12-07T03:25:05.843 回答
2

I wrote an 8-puzzle solver in Lisp about a year ago. I just used a list of 3 lists, each sublist with 3 elements being the numbers. It's not constant time, but it is portable.

Anyways, if you are really interested in doing this functionally (Scheme doesn't require you to) what is easiest to do is to create some helper functions that will get a specific value given row/col and 'set' a value given row/col. Instead of modifying the original data structure, the set operation will construct the new state based on the old state.

Then you can write a swap operation based on these get and set operations. Here's what I wrote about a year ago in Common Lisp, but it's easily convertible to 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

这是实现它的一种方法。使用将应用适当映射的函数重新创建列表。

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。这一次，我一直在玩scheme，但想使用python，所以如果我被困在某些东西上，我可以“作弊”并使用pythonish，然后在等待usenet答案的同时继续问题的下一部分.

于 2008-12-07T07:40:26.610 回答