0

我正在学习 Scheme，作为一个玩具示例，我正在为 Hanoi Towers 做一个解决方案验证器（不是求解器）。我想使用纯粹的功能风格（只是为了进入心态），我将塔表示为三个列表的简单列表。起始状态可能如下所示：'((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。

4

1 回答 1

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”，它可以在单个塔上返回您的命令结果，这就是使解决方案的其余部分变得非常简单的原因。

由于您要求提供反馈，我注意到当应用于数字时，Scheme 中的内部工作和您期望的行为（例如，您可以递归调用它们）=是相同的，并且 Lisp 中通常的命名约定是将多个-带有连字符的单词标识符，而不是使用驼峰式。祝你好运！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自己的上述版本。

于 2011-09-28T16:08:05.337 回答