Lisp最佳實踐

Question

我已經在2天前開始學習Lisp，並且正在閱讀Paul Graham的ANSI Common List，它以非常有趣的方式公開了語言結構。對於初學者來說，這不是太理論，也不是太淺（正如Sierra-Bate的Head First Java，我個人討厭）。在簡短的通用語言介紹之後，他開始討論回合列表並舉出一個簡單列表壓縮的例子。基本上，讓el是一個重複n次的元素。你用一個單獨的列表替換所有的列表。要做到這一點，他給了代碼實現，但我試圖做我自己的，這顯然是工作。如果可能的話，我希望有人分析我的代碼並告訴我它的實現的關鍵點，我相信這有很多，因爲它是我第一次接觸Lisp。謝謝大家！

(defun compress (x) 
"compress a list replacing repeated sequential values for (<n> <value>)" 
(let ((lst '()) (fst t) (lt nil) (n 0)) 
    (dolist (el x) 
     (if fst 
      (progn 
       (setq fst nil) 
       (setq lt el) 
       (setq n 1)) 
      (progn 
       (if (equal el lt) 
        (setq n (+ n 1)) 
        (progn 
         (setq lst (cons (if (= n 1) 
            lt 
            (list n lt)) 
           lst)) 
         (setq lt el) 
         (setq n 1) 
        ))))) 
    (setq lst (cons (if (and (not (= n 0)) (= n 1)) 
         lt 
         (list n lt)) 
      lst)) 
(reverse lst))) 

Answer 1

算法看起來很合理。我只發現fst變量多餘。只有在進入循環時才使用它，因此您可以將第一批賦值移至前導碼，並遍歷列表的其餘元素。

現在的問題是如何在Lisp中表達算法。

最重要的一點是，您可以使用nreverse而不是reverse。 nreverse更有效，但它破壞了它的論證結構。一般來說，由於所謂的共享結構，你不希望這樣做：一個cons cell可能是少數列表的一部分，所以修改一個缺點可能會導致明顯不相關的列表出現意​​外的變化。 （PCL很好地處理這個問題。）然而，在你的函數中，你從零開始構建lst，手動將新元素推送到它上面，所以它不可能與其他列表共享結構。所以你可以放心地放棄結構。這是常見的push/nreverse習語。 reverse剛剛新建一個列表，並且lst變成垃圾。

要使代碼更具慣用性，您可以使用標準快捷方式，如incf代替+=和push代替cons=。如今通用setf似乎更受歡迎，然後setq。就個人而言，我更喜歡使用cond，否則progn會出現。所以，你可能最終會像這樣的東西：

(defun compress (x) 
    "compress a list replacing repeated sequential values for (<n> <value>)" 
    (if x 
     (let ((lst '()) 
      (lt (first x)) 
      (n 1)) 
     (dolist (el (rest x)) 
      (cond ((equal el lt) (incf n)) 
       (t (push (if (= n 1) 
          lt 
          (list n lt)) 
         lst) 
        (setf lt el) 
        (setf n 1)))) 
     (push (if (= n 1) 
        lt 
        (list n lt)) 
       lst) 
     (nreverse lst)) 
     nil)) 

Answer 2

除了Stanislav's answer 我想顯示一種可能的實現。 壓縮算法是REDUCE的完美使用案例，也稱爲fold。 reduce函數到目前爲止取得了一個新元素的結果，並將它們結合起來以產生下一個結果。你想要的結果是夫婦的列表。最初的元素是空列表。

(defun compress (sequence) 
    (reduce (lambda (number list &aux (head (first list))) 
      (if (eql number (first head)) 
       (prog1 list 
        (incf (second head))) 
       (cons (list number 1) list))) 
      sequence 
      :from-end t 
      :initial-value nil)) 

減少從結束應用，讓您可以輕鬆地cons一對新人在當前結果的頂部，同時保持元素的現有秩序。如果你輸入'(a b b c)，那麼匿名還原功能將被調用如下：

number list   new list 
--------------------------------------------- 
c  nil   ((c 1)) 
b  ((c 1))  ((b 1)(c 1)) 
b  ((b 1)(c 1)) ((b 2)(c 1)) 
a  ((b 2)(c 1)) ((a 1)(b 2)(c 1)) 

REDUCE正在爲序列定義，壓縮功能是通用的：

;; string 
(compress "aaddzadzaaaddb") 
=> ((#\a 2) (#\d 2) (#\z 1) (#\a 1) (#\d 1) (#\z 1) (#\a 3) (#\d 2) (#\b 1)) 

;; vector 
(compress #(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5)) 
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6)) 

;; list 
(compress '(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5)) 
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6))