Вопросы по преобразованию python-> схемы

Question

В настоящее время я пытаюсь написать программу на Python, используя семантику схемы, чтобы впоследствии я мог перевести ее на Scheme, не полагаясь на много Pythonic.

Я пытаюсь решить проблему со скользящей головоломкой (где у вас есть 9 слотов и 8 плиток, расположенных в квадрате), используя алгоритм поиска *, глубина вначале и ширина вначале. Я делал это ~ 11 лет назад в каком-то ИИ-классе на Лиспе, но в основном в то время я не имел понятия о Лиспе, я ненавидел его всем сердцем, и только в ретроспективе я понял, что программирую «С» на Лиспе. Проф не помог в этом деле.

У меня есть функция 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 !, и не прибегая к сумасшествию, если / then / else предложения относительно того, какой элемент должен быть изменен. Это, конечно, становится более запутанным при рассмотрении 2d-массива. В этом случае решение с python очевидно из-за его собственной поддержки многомерных массивов.

В C / C ++ / Python / Matlab / Lua / что-либо еще доступ к спискам / массивам с помощью синтаксиса [i] является простым и напрямую переводится в поиск аппаратно-ориентированных указателей где-то внизу. Я не понимаю, как схема делает это, учитывая атомарные операции, определенные в SICP-версии схемы, которые кажутся очень ориентированными на цикл и поиск. Как работают функции доступа к массиву векторов и списков для получения постоянного доступа? (Я здесь новичок, поэтому не знаю, о каких функциях я буду говорить). Есть ли где-нибудь библиотека C или Assembly, к которой есть тайный доступ? Есть ли в схеме какая-то внутренняя семантика с постоянным временем, которую можно было бы использовать для доступа к списку / массиву / вектору, и которая позволила бы мне на данный момент безошибочно использовать эту идиому в Python?

Как бы я мог переписать вышеуказанную функцию в python, используя семантику Schemish? Как бы я переписал вышеуказанную функцию на схеме?

Answer 1

Вы определили, что вашей первоначальной проблемой была попытка написать семантику C на Лиспе. Не повторяется ли ошибка, пытаясь написать семантику схемы в python? Я всегда стараюсь выучить язык X как парадигму так же, как и язык, и пишу самым странным образом.

Возможно, было бы оправданно, если бы это было бизнес-приложение, которое, как вы знали, должно было быть перенесено, но в противном случае я бы просто написал его в схеме для начала.

Answer 2

Я написал решатель из 8 задач на Лиспе около года назад. Я просто использовал список из 3 списков, каждый из которых состоит из 3 элементов. Это не постоянное время, но оно переносимо.

В любом случае, если вы действительно заинтересованы в том, чтобы делать это функционально (схема не требует от вас), то проще всего создать несколько вспомогательных функций, которые получат конкретное значение, заданное в строке / столбце, и «установить» значение данный ряд / цв. Вместо изменения исходной структуры данных операция set создаст новое состояние на основе старого состояния.

Затем вы можете написать операцию подкачки на основе этих операций 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. Я должен изучить это, чтобы удостовериться, что я получаю это.

Что касается первого ответа, то в первый раз я «писал c» на lisp, потому что это единственный способ, которым я знал, как программировать, и понятия не имел, почему кто-то будет использовать lisp. На этот раз я поигрался со схемой, но хотел использовать python, поэтому, если я застрял на чем-то, я мог бы «обмануть» и использовать что-то на pythonish, а затем, ожидая ответов usenet, перейти к следующей части проблемы .