Python转Scheme转换问题
我现在正在尝试写一个Python程序，使用Scheme的语义，这样我以后可以把它翻译成Scheme，而不需要依赖很多Python特有的东西。
我想用A*算法、深度优先搜索和广度优先搜索来解决滑块拼图问题（就是有9个格子，里面放着8个拼图块，拼图块可以滑动）。大约11年前我在某个人工智能课程上用Lisp做过这个，但当时我对Lisp一无所知，甚至非常讨厌它，回想起来我发现我其实是在用Lisp写“C”语言。教授在这方面也没有给我太多帮助。
我有一个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
我想把这个函数改成你在《计算机程序的构造和解释》中可能会看到的样子，避免副作用等等。
但这引出了一个问题。我在《计算机程序的构造和解释》中看到的所有循环都是通过递归实现的。我没有看到任何关于如何以恒定时间访问数组、向量或列表的内容。我能想象出一种循环或递归的方式来读取一个元素，但我觉得更难想象如何在不使用像set!这样的会产生副作用的东西，也不需要复杂的if/then/else语句来决定哪个元素应该被改变的情况下，创建一个新的列表，改变某个元素。当然，当考虑到二维数组时，这就更让人困惑了。在这种情况下，使用Python的解决方案显而易见，因为它原生支持多维数组。
在C/C++/Python/Matlab/Lua/其他任何语言中，通过[i]语法访问列表/数组是很简单的，这直接对应于底层硬件的指针查找。我不明白Scheme是怎么做到这一点的，考虑到《计算机程序的构造和解释》中定义的原子操作似乎都是围绕循环和搜索的。向量和列表的数组访问函数是如何实现恒定时间访问的？（我在这方面完全是新手，所以我甚至不确定我在说哪些函数）。是否有某个C或汇编库在背后被秘密调用？在Scheme中是否有任何固有的恒定时间语义可以用于列表/数组/向量的访问，这样我就可以在Python中无负担地使用这种习惯？
我该如何用Scheme的语义重写上面的Python函数？我该如何用Scheme重写上面的函数？
4 个回答
这里有一种方法可以实现这个目标。你可以用一个函数来重新创建列表，这个函数会应用适当的映射。
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]]
我大约一年前用Lisp写了一个8数码游戏的解法程序。我用的是一个包含3个列表的列表，每个子列表有3个元素，代表数字。虽然这个方法不是常量时间的，但它很方便移植。
如果你真的想用函数式编程来实现这个功能（其实Scheme并不强制你这样做），最简单的方法就是创建一些辅助函数，这些函数可以根据行和列来获取特定的值，或者根据行和列来设置一个值。这样做的好处是，不会直接修改原来的数据结构，而是根据旧的状态构建新的状态。
接着，你可以基于这些获取和设置操作来写一个交换操作。下面是我大约一年前在Common Lisp中写的代码，不过很容易转换成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))))
你发现自己最开始的问题是试图用Lisp来写C语言的风格。那你是不是又在犯同样的错误，试图用Python来写Scheme的风格呢？我总是努力把学习的语言X当作一种思维方式来理解，同时尽量用最符合X语言特点的方式来编程。
如果这是一个你知道会迁移到其他平台的商业应用，那这样做可能是合理的，但如果不是的话，我建议你一开始就直接用Scheme来写。