在河內的塔樓移動光盤的習慣性功能方式

Question

我正在學習Scheme，並且作爲一個玩具的例子，我正在爲河內的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.

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功能，有多種語言和庫的標準，但沒有內置方案的存在，那麼你可以捲起底部組的每個塔的操作進入到一個呼叫，它會更乾淨。

一般來說，嘗試提出純粹的功能降到最低的水平，做你想做的事。在這個解決方案中，我發明了一個純粹的函數「alter-tower」，它可以在單個塔上返回命令的結果，這就是解決方案其餘部分非常簡單的原因。

既然你問意見，我注意到，當應用於數字=是eqv?相同，與在方案內部defines工作，正如你所期望的行爲（例如，您可以遞歸調用它們），而通常的命名約定在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) 

所以根據您的方案方言和庫它可能是不同的：喜歡看。 （我認爲這不是一個SRFI，但我可能弄錯了。）或者你總是可以自己編寫以上版本的map。