Идиоматический функциональный способ перемещения диска в Towers of Hanoi

Question

Я изучаю Scheme, и в качестве примера я делаю проверку решения (а не решателя) для Towers of Hanoi. Я хочу использовать чисто функциональный стиль (просто для того, чтобы войти в образ мыслей) и представляю башню в виде простого списка из трех списков. Начальное состояние может выглядеть примерно так: '((0 1 2 3 4) () ())

Как мне реализовать функцию, которая принимает состояние, исходный индекс и целевой индекс и возвращает новое состояние? В императивном стиле это было бы что-то тривиальное, как:

state[target].push(state[source].pop())

Но каждое функциональное решение, которое я могу придумать, ужасно запутано. Например:

(define (makeMove state source target)
  (letrec ((recMake (lambda(tower pos disc)
              (if (null? tower) '()
              (cons (if (eqv? pos source)
                    (cdr (car tower))
                    (if (eqv? pos target) 
                    (cons disc (car tower))
                    (car tower)))
                (recMake (cdr tower)
                     (+ pos 1)
                     disc))))))
    (recMake state 0 (car (list-ref state source)))))

Кажется, это работает, но должен быть лучший способ. Я предполагаю, что карта была бы несколько лучше, чем рекурсия, но все же слишком много. Было бы проще, если бы я представлял государство по-другому?

Кроме того, не стесняйтесь критиковать мой код. Я действительно не знаю, что я делаю.

РЕДАКТИРОВАТЬ: Если возможно, я предпочитаю, чтобы вы не предполагали, что количество башен всегда 3.

Answer 1

Вот супер-простой способ. Я не уверен, какое значение имеют "цифры" диска в вашей реализации, но я заставил его вести себя так же, как ваш ответ, нажимая и выталкивая их.

(define (make-move state source target)
  (define (alter-tower tower index disc)
    (cond ((= index source) (cdr tower))       ; remove a disc
          ((= index target) (cons disc tower)) ; add a disc
          (else tower)))                       ; this tower wasn't changed
  (let ((disc (car (list-ref state source))))
    (let ((s0 (alter-tower (list-ref state 0) 0 disc))
          (s1 (alter-tower (list-ref state 1) 1 disc))
          (s2 (alter-tower (list-ref state 2) 2 disc)))
      (list s0 s1 s2))))

Если вы предполагаете существование map-with-index Функция, которая является стандартной во многих языках и библиотеках, но не встроена в Scheme, тогда вы можете свернуть нижний набор операций на каждой башне в вызов этого, и это будет гораздо чище.

В общем, старайтесь придумать чистые функции до минимально возможного уровня, которые делают то, что вы хотите. В этом решении я изобрел чистую функцию "alter-tower", которая может возвращать результат вашей команды на одной башне, и это делает остальную часть решения очень простой.

Так как вы просили оставить отзыв, отмечу, что = идентичен для eqv? применительно к номерам, которые внутренние defines работать в Scheme и действовать так, как вы ожидаете (например, вы можете вызывать их рекурсивно), и что обычное соглашение об именах в Lisp состоит в том, чтобы разделять идентификаторы из нескольких слов с дефисами вместо использования верблюда. Удачи!

РЕДАКТИРОВАТЬ: Вот версия, например, которая использует понимание списка Racket:

(define (make-move state source target)
  (define (alter-tower tower index disc)
    (cond ((= index source) (cdr tower))       ; remove a disc
          ((= index target) (cons disc tower)) ; add a disc
          (else tower)))                       ; this tower wasn't changed
  (let ((disc (car (list-ref state source))))
    (for/list ([(tower idx) (in-indexed state)])
      (alter-tower tower idx disc))))

Многие функциональные языки имеют map это может принимать предикат, который использует индекс, поэтому эти две строки могут выглядеть следующим образом:

(map (lambda (tower idx) (alter-tower tower idx disc)) state)

Так что в зависимости от вашего диалекта Scheme и библиотек он может отличаться. (Я не думаю, что для этого есть SRFI, но я могу ошибаться.) Или вы всегда можете написать вышеуказанную версию map сам.