Блог

Я изучаю схему и в качестве игрушечного примера я делаю средство проверки решения (а не решатель) для башен Ханоя. Я хочу использовать чисто функциональный стиль (просто чтобы войти в мышление), и я представляю башню в виде простого списка из трех списков. Начальное состояние может выглядеть примерно так: ‘((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.

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

 (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))))
  

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

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

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