3

两天前我开始学习 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)))
4

2 回答 2

3

该算法似乎很合理。我只发现fst变量是多余的。您仅在进入循环时才使用它，因此您也可以将第一组分配移动到前导码并迭代列表的其余元素。

现在的问题是如何在 Lisp 中表达算法。

最重要的一点是您可以使用nreverse代替reverse. nreverse更有效，但它破坏了其论证的结构。通常，由于所谓的共享结构，您不希望这样做：一个 cons 单元格可以是几个列表的一部分，因此修改 cons sell 您可能会在明显不相关的列表中带来意想不到的变化。（PCL 很好地处理了这个问题。）但是，在您lst从头开始构建的函数中，手动将新元素推送到它上面，因此它无法与其他列表共享结构。因此，您可以放心地省去该结构。这是常见的push/nreverse成语。 reverse只是消耗了一个新的列表，lst变成了垃圾。

为了使代码更惯用，您可以使用标准快捷方式，例如incffor+=和pushfor cons=。现在通用setf似乎更受欢迎setq。就个人而言，我更喜欢使用condaprogn否则会出现的地方。所以你最终可能会得到这样的结果：

(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))
于 2015-10-06T12:32:57.747 回答
3

除了斯坦尼斯拉夫的回答 ，我想展示另一种可能的实现。压缩算法是一个完美的用例 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))
于 2015-10-06T14:16:07.130 回答