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

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

0 голосов
/ 28 сентября 2011

Я изучаю 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)))))

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

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

EDIT: Если возможно, я предпочитаю, чтобы вы не предполагали, что количество башен всегда равно 3.

1 Ответ

1 голос
/ 28 сентября 2011

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

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

РЕДАКТИРОВАТЬ: Вот, например, версия, которая использует 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 самостоятельно.

...