Lisp語言 - 編寫評估圖形節點的功能標籤

Question

考慮的圖形像這樣，節點和鄰居組成：

(defparameter *graph* '((A (B C D)) 
         (B (A C E)) 
         (C (A B D E)) 
         (D (A C E)) 
         (E (B C D)))) 

...併爲每個節點一組標籤：

(defparameter *values* '((A 1) 
         (B 2) 
         (C 3) 
         (D 2) 
         (E 1))) 

我試圖編寫一個函數來評估該格式的圖形，並確定相鄰節點是否具有相同的標籤。如果我在C++或Java我的邏輯寫這個的函數的迭代版本可能是這個樣子：

(defun evaluate-label (graph values) 
;; for every node in graph 
    ;; for every adjoining node 
    ;; if (node.value == adjoiningNode.value) 
     ;; return false 
;; return true 
) 

...但我不知道什麼樣的邏輯將是更適合的Lisp ，更不用說如何去編碼它了。

於是，兩個問題：

1. 將僞的此功能的「Lispy」有點什麼樣子？
2. 你會在函數中加入什麼特定的語法特徵？我們假設有一個cond。 every是否對這個問題有用？我們可以輕鬆做到這一點，而不訴諸lambda表達式？

在此先感謝您的任何反饋意見！

Answer 1

良好的編程的一個重要方面，無論語言如何，都是很好的抽象。有時候，這可能是一個有趣的問題，但這裏有一個例子試圖對這個問題應用一些抽象。一旦獲得了圖形和值，就可以定義一個返回節點值的節點值函數。然後你可以將你的問題描述爲

有沒有某個節點的圖形與其鄰居有相同的節點值？

這是不是太難用寫一些：

(defun adjacent-values-p (graph values) 
    (flet ((node-value (node) 
      (cadr (assoc node values)))) 
    (some #'(lambda (node-descriptor) 
       (destructuring-bind (node neighbors) 
        node-descriptor 
       (find (node-value node) neighbors 
         :key #'node-value))) 
      graph))) 

(adjacent-values-p '((a (b c))) 
        '((a 1) (b 2) (c 1))) 
;=> C 

(adjacent-values-p '((a (b c))) 
        '((a 1) (b 2) (c 3))) 
;=> NIL 

這就是說，儘管這可能是更多的Lisp-Y在某種意義上，它使用明確的迭代來編寫它可能同樣有意義dolist：

(defun adjacent-values-p (graph values) 
    (flet ((node-value (node) 
      (cadr (assoc node values)))) 
    (dolist (node-descriptor graph) 
     (destructuring-bind (node neighbors) node-descriptor 
     (when (member (node-value node) neighbors :key #'node-value) 
      (return t)))))) 

這可以更好的與環，它支持一些解構：

(defun adjacent-values-p (graph values) 
    (flet ((node-value (node) 
      (cadr (assoc node values)))) 
    (loop for (node neighbors) in graph 
     thereis (find (node-value node) neighbors :key #'node-value)))) 

所有這些版本可以從存儲的值，e.g受益，。一個快速檢索的散列表。這是否有意義取決於您的需求，應用領域等。否則，您將檢索邊標籤O（2 × | E |），每次都執行O（| V |）遍歷。例如：

(let ((table (make-hash-table))) 
    (flet ((node-value (node) 
      (multiple-value-bind (value presentp) 
       (gethash node table) 
      (if presentp value 
       (setf (gethash node table) 
         (cadr (assoc node values))))))) 
    ;; ... 
    )) 

通過在需要時不查找節點值來緩存「按需」。但是，由於應該需要每個節點值（假設提供的值列表不包含任何額外的節點），所以最好在開始時填充表。那麼你以後不必做任何檢查，你只需要遍歷值列表一次。因此：

(defun adjacent-values-p (graph values &aux (table (make-hash-table))) 
    (loop for (node value) in values 
    doing (setf (gethash node table) value)) 
    (flet ((node-value (node) 
      (gethash node table))) 
    ;; ... 
    ))