Lisp 良好实践

Question

我 2 天前开始学习 Lisp，我正在阅读 Paul Graham 的 ANSI Common List，它以一种非常有趣的方式揭示了语言结构。对于初学者来说，这不是太多的理论，也不是太浅（如 Sierra-Bate 的 Head First Java，我个人讨厌）。在简要介绍了一般语言之后，他开始谈论列表并举了一个简单列表压缩的例子。基本上，让 el 成为重复 n 次的元素。您用一个 (n el) 列表替换所有这些。为此，他提供了一个代码实现，但我尝试自己实现，这显然是可行的。如果可能的话，我希望有人分析我的代码并向我展示其实现的关键点，我确信这有很多，因为这是我第一次接触 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 可以是几个列表的一部分，因此修改 cons sell 可能会给看似无关的列表带来意想不到的变化。（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

除了我想展示另一种可能的实现方式。压缩算法是 REDUCE, also known as fold 的完美用例。 reducing 函数获取到目前为止的结果，一个新元素，并将它们组合起来产生下一个结果。您想要的结果是一对夫妇的列表。初始元素是空列表。

(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))

Lisp 良好实践

Lisp good practices

lisp

algorithm

common-lisp

ansi-common-lisp