python->scheme转换的问题

Question

我目前正在尝试使用方案语义编写一个Python程序，这样我以后就可以将其转换为Scheme，而无需依赖大量Pythonic的东西。

我正在尝试使用 a*、深度优先和广度优先搜索算法来解决滑动拼图问题（其中有 9 个插槽和 8 个方块排列在一个正方形中）。 我大约 11 年前在 Lisp 的一些 AI 课程中这样做过，但基本上当时我对 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  

我想将其转换为您可能在 SICP 中找到的东西，避免副作用等。

但这提出了一个问题。 我在 SICP 中读到的所有内容都是通过递归进行循环。 我没有看到在恒定时间内访问数组/向量/列表的任何内容。 我可以想象一种循环/递归的方式来读取元素，但我发现很难想象一种方法来创建一个更改了某个元素的新列表，而不调用产生诸如 set! 之类的副作用，并且不诉诸疯狂的 if /then/else 子句涉及应更改哪个元素。 当考虑二维数组时，这当然会变得更加混乱。 在这种情况下，使用 python 的解决方案是显而易见的，因为它本身支持多维数组。

在 C/C++/Python/Matlab/Lua/其他任何语言中，通过 [i] 语法访问列表/数组很容易，并且直接转换为底层面向硬件的指针查找。 我不明白scheme是如何做到这一点的，因为scheme的SICP版本中定义了原子操作，这些操作看起来都非常面向循环和搜索。 矢量和列表数组访问函数如何获得恒定时间访问？ （我是这里的新手，所以我不确定我会谈论什么功能）。 是否有 C 或汇编库正在被秘密访问？ 方案中是否有任何固有的常量时间语义可用于列表/数组/向量访问，并且这将允许我暂时在 Python 中使用该习惯用法而无负罪感？

如何使用 Schemish 语义在 python 中重写上述函数？ 我如何在Scheme中重写上述函数？

Answer 1

您发现最初的问题是尝试用 Lisp 编写 C 语义。 尝试用python写scheme语义不是在重蹈覆辙吗？ 我总是尝试将 X 语言作为一种范式来学习，就像学习一种语言一样，并以最 X 风格的方式进行写作。

如果这是一个您知道将要迁移的业务应用程序，那么这可能是合理的，但否则我只是一开始就将其编写在方案中。

Answer 2

大约一年前，我用 Lisp 编写了一个 8 谜题求解器。 我只使用了 3 个列表的列表，每个子列表有 3 个元素是数字。 它不是恒定时间，但它是可移植的。

无论如何，如果您真的有兴趣在功能上执行此操作（方案不要求您这样做），最简单的方法是创建一些辅助函数，这些函数将获取给定行/列的特定值并“设置”给定行/的值上校 设置操作不会修改原始数据结构，而是基于旧状态构造新状态。

然后你可以根据这些get和set操作编写一个交换操作。 这是我一年前在 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))))

Answer 3

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

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]]

Answer 4

酷，谢谢你的 lisp 代码。 我需要研究它以确保我明白。

至于第一个答案，我第一次用 lisp“写 c”，因为这是我知道如何编程的唯一方法，并且不知道为什么有人会使用 lisp。 这一次，我一直在玩scheme，但想使用python，所以如果我陷入困境，我可以“作弊”并使用pythonish，然后在等待usenet答案的同时继续解决问题的下一部分。