优雅的方式来计算项目

Question

我有一个如下所示的列表：

  '(("Alpha" .  1538)
    ("Beta"  .  8036)
    ("Gamma" .  8990)
    ("Beta"  .  10052)
    ("Alpha" .  12837)
    ("Beta"  .  13634)
    ("Beta"  .  14977)
    ("Beta"  .  15719)
    ("Alpha" .  17075)
    ("Rho"   .  18949)
    ("Gamma" .  21118)
    ("Gamma" .  26923)
    ("Alpha" .  31609))

如何计算列表中每个元素在汽车中出现的术语总数？基本上我想：

(("Alpha" . 4)
 ("Beta" . 5)
 ("Gamma" . 3)
 ("Rho" . 1))

不，这不是作业。我只是还没有掌握“用 Lisp 思考”的东西。

在 C# 中，我会使用 LINQ 来完成此操作。我也可以在 lisp 中使用 while 循环等来做到这一点，但我考虑的方式似乎过于复杂。

---

编辑

这就是我所拥有的：

(defun count-uniq (list)
  "Returns an alist, each item is a cons cell where the car is
a unique element of LIST, and the cdr is the number of occurrences of that
unique element in the list. "
  (flet ((helper (list new)
                 (if (null list)
                     new
                   (let ((elt (assoc (car list) new)))
                     (helper (cdr list)
                             (if elt
                                 (progn (incf (cdr elt)) new)
                               (cons (cons (car list) 1) new)))))))
    (nreverse (helper list nil))))

Answer 1

(defun freqs (list &optional test key)
  (let ((h (make-hash-table :test test)))
    (dolist (x list)
      (let ((key (if key (funcall key x) x)))
        (puthash key (1+ (gethash key h 0)) h)))
    (let ((r nil))
      (maphash #'(lambda (k v) (push (cons k v) r)) h)
      (sort r #'(lambda (x y) (< (cdr x) (cdr y)))))))

(freqs '(("Alpha" .  1538)
         ("Beta"  .  8036)
         ("Gamma" .  8990)
         ("Beta"  .  10052)
         ("Alpha" .  12837)
         ("Beta"  .  13634)
         ("Beta"  .  14977)
         ("Beta"  .  15719)
         ("Alpha" .  17075)
         ("Rho"   .  18949)
         ("Gamma" .  21118)
         ("Gamma" .  26923)
         ("Alpha" .  31609))
       #'equal #'car)

Answer 2

组合更高级别的 Common Lisp 函数：

(defun count-unique (alist) 
  (mapcar
    (lambda (item)
      (cons (car item)
            (count (car item) alist :test #'equal :key #'car)))
    (remove-duplicates alist :test #'equal :key #'car)))

但它不能扩展到大型列表。如果您需要 O(n) 性能，请使用基于哈希表的解决方案，例如不太优雅的方案：

(defun count-unique (alist)
  (loop
     with hash = (make-hash-table :test #'equal)
     for (key . nil) in alist
     do (incf (gethash key hash 0))
     finally (return
               (loop for key being each hash-key of hash
                  using (hash-value value)
                  collect (cons key value)))))

Answer 3

我不知道这是最优雅的，但看起来很合理：

(defun add-for-cheeso (data)
  (let (result)
    (dolist (elt data result)
      (let ((sofar (assoc (car elt) result)))
        (if sofar
            (setcdr sofar (1+ (cdr sofar)))
          (push (cons (car elt) 1) result))))))

Answer 4

使用 Common Lisp 扩展：

(require 'cl)
(loop with result = nil
      for (key . dummy) in original-list
      do (incf (cdr (or (assoc key result)
                        (first (push (cons key 0) result)))))
      finally return (sort result
                           (lambda (a b) (string< (car a) (car b)))))

如果您不关心对最终结果进行排序，您可以直接说 finally return result。

Answer 5

每次你想要遍历一个列表并返回一些值时，无论是一个新列表还是一些聚合结果，你都会想到一个 fold，在 Python 和 Lisps 中也称为“reduce”。 Fold 是一个很好的抽象，因为它允许编写通用代码，只需调整一些元素即可适用于许多用例。求几个数字的和、求乘积、求最小整数之间有什么相似之处？它们都是折叠，因为您遍历列表，然后根据其内容返回一些结果。在 Emacs Lisp 中，它们看起来像这样：

(reduce '+ '(1 2 3 4 5)) ; 15
(reduce '* '(1 2 3 4 5)) ; 120
(reduce 'min '(1 2 3 4 5)) ; 1

但折叠比这更普遍。求和、计算列表中偶数的个数、删除每个奇数以及建立一个每个数字都增加 5 的列表之间有什么相似之处？每个这样的函数都可以通过取一些基值，依次对其进行变换，直到得到结果来实现。您采用这个基值（隐喻的粘土团），将其称为“累加器”，然后从列表中取出一个元素，并基于该元素对这个粘土团进行一些操作，使其成为一个宏伟雕塑的草稿。然后你从列表中取出下一个元素并对你的雕塑做一些新的事情。你重复这个直到列表为空，你最终得到了一个杰作。就好像列表中的每个元素都是一个大配方中的单个指令。请记住，您可以完全自由地对粘土执行任何操作，不必直接使用结果中的列表元素 - 从技术上讲，这意味着累加器（以及结果）可能是不同的类型。

(reduce '+ '(1 2 3 4 5) :initial-value 0) ; 15
(reduce (lambda (acc x) (if (evenp x) (1+ acc) acc)) '(1 2 3 4 5) :initial-value 0) ; 2
(reduce (lambda (x acc) (if (oddp x) acc (cons x acc))) '(1 2 3 4 5) :initial-value '() :from-end t) ; (2 4)
(reduce (lambda (x acc) (cons (+ x 5) acc)) '(1 2 3 4 5) :initial-value '() :from-end t) ; (6 7 8 9 10)

关于从末尾减少的注意事项：Lisps 中的列表不是像 Python 或 Java 中那样的智能数组，它们是链接列表，因此访问或更改列表中某处的元素是一个 O(n) 操作，而“consing”到列表的开头时间复杂度为 O(1)。换句话说，将一个元素追加到列表的末尾是昂贵的，因此 Lispers 通常将元素添加到列表的开头，然后最后反转列表，这称为 push/nreverse习语。如果我们在最后两个函数中进行普通的reduce，我们将cons 1到累加器并得到(1)，然后将cons 2到累加器并得到(2 1)，直到我们得到正确的结果但颠倒了。之后我们可以使用 reverse 函数，但幸运的是 Emacs 的 reduce 支持 :from-end 关键字参数，所以它 cons 5，然后 4，然后 3 ，等等。

现在很清楚，您的操作是折叠，遍历原始列表并计算每个键的出现次数。在写我们的折叠之前，让我们先谈谈 alist。 Lisp 中的 Alist 是一个穷人的哈希表。您通常不会修改编程语言的哈希表实现细节，是吗？您使用 API。在 Python 中，此 API 看起来像方括号语法 (d['a'] = 1) 和 dict 方法 (d.keys())。对于 alists API 包含函数 assoc，它返回提供密钥的项目。

(assoc 'a '((a . 1) (b . 2))) ; (a . 1)

为什么我要讲实施细节？因为您通过 assoc 工作，并且您不关心这个 alist到底 是什么样子，所以您可以将其抽象化。 API 的另一部分是，如果您想添加新元素或更改现有元素，只需将点对添加到列表中即可。这就是你应该如何与 alist 一起工作，无论其内部结构如何。为什么这样有效？例如，如果我想将键 a 的值更改为 10，我只需运行 (cons '(a . 10) my-alist) 和 my-alist 最终将是 '((a . 10) (a . 1) (b . 2))。但这没问题，因为 assoc 仅返回第一个点对，而忽略其余部分，因此您可以像对待任何其他键值数据结构一样对待 alist。考虑到这一点，让我们来编写我们的第一个严肃的折叠。

(reduce (lambda (acc x)
          (let* ((key (car x))
                 (pair (assoc key acc))
                 (count (cdr pair)))
            (if pair
                (cons (cons key (1+ count)) acc)
              (cons (cons key 1) acc))))
        my-alist
        :initial-value '())

这里会发生什么？我们获取您的数据和一个空列表，这很快就会成为我们想要的结果。在每一步中，我们都会从数据中获取一对并询问：我们的结果是否包含有关该对的信息？如果没有，那么我们将其添加到结果中并放入 1——我们第一次遇到这个键。但是，如果我们确实在结果中找到了有关该对的信息，那么我们必须再次将其添加到我们的结果中，但这次数字增加 1。对数据中的每个项目重复该过程，您将得到：

(("Alpha" . 4) ("Gamma" . 3) ("Gamma" . 2) ("Rho" . 1) ("Alpha" . 3)
 ("Beta" . 5) ("Beta" . 4) ("Beta" . 3) ("Alpha" . 2) ("Beta" . 2)
 ("Gamma" . 1) ("Beta" . 1) ("Alpha" . 1))

请记住assoc 只关心某个键的第一次出现？该 alist 的行为与 (("Alpha" . 4) ("Gamma" . 3) ("Rho" . 1) ("Beta" . 5)) 相同，因此我们在这里很好。不过，我们是否可以改变折叠以获得后者更短的结果？等等，如果我们可以事后调整结果，那么有什么必要让我们的折叠变得过于复杂呢？毕竟，如果不是一系列数据转换，那么什么是计算机编程呢？您没有理由不能从列表中删除所有“过时”对，只需 使用 cl-remove-使用正确的参数重复，就完成了。

所以我们为自己感到自豪，我们编写了一个折叠，这是函数式编程的支柱，但仔细检查会发现效率低下：我们用 assoc 遍历累加器以找到一对及其要递增的值。 assoc 需要 O(n)，reduce 本身需要 O(n)，因此我们的算法是 O(n²)（了解 增长顺序，如果你不明白大 O 表示法）。很明显，我们应该更好地使用适当优化的哈希表，并在需要时将其转换为列表。重写我们的折叠：

(reduce (lambda (acc x)
          (cl-incf (gethash (car x) acc 0))
          acc)
        my-alist
        :initial-value (make-hash-table :test 'equal))

(gethash kd 0) 相当于 Python 的 d.get('k', 0)，其中最后一个参数是默认值。 cl-incf（Common Lisp 等价的 incf）是一个智能宏，可以就地增加其参数（请阅读 setf 了解智能分配）。 make-hash-table 需要自定义测试函数，因为字符串无法与默认的 eql 函数进行比较。要获得 alist，只需使用 ht->alist 函数转换我们折叠的结果哈希表，我们可以从 Wilfred 的 ht.el 库，或者我们自己编写：

(defun ht->alist (table)
  (let (alist)
    (maphash (lambda (k v)
               (push (cons k v) alist))
             table)
    alist))

Answer 6

(require 'cl)
(defun count-uniq (list)
  (let ((k 1) (list (sort (mapcar #'car list) #'string<)))
    (loop for (i . j) on list
          when (string= i (car j)) do (incf k)
          else collect (cons i k) and do (setf k 1))))

Answer 7

使用高阶函数sort和reduce。

首先排序（使用 string<），然后减少（计算 cons 单元格中连续的 string= 值）：

(reduce (lambda (r e)
          (if (and r (string= (caar r) e))
              (cons
               (cons (caar r) (1+ (cdar r)))
               (cdr r))
            (cons (cons e  1) r)))
        (sort (mapcar 'car alist) 'string<)
        :initial-value nil)

Answer 8

使用 dash 库，这非常简单明了：

(require 'dash)    
(-frequencies (mapcar #'car my-list))

-frequencies 在 v2.20.0 中引入。

Answer 9

我认为这是一个使用 Emacs 的 alist 函数的优雅的函数解决方案，产生一个可重用的 frequencies 函数，类似于 Eli 的答案：

(defun frequencies (vals)
  (reduce
   (lambda (freqs key)
     (cons (cons key (+ 1 (or (cdr (assoc key freqs)) 0)))
           (assq-delete-all-with-test key freqs 'equal)))
   vals
   :initial-value nil)))

(frequencies (mapcar 'car
                     '(("Alpha" .  1538)
                       ("Beta"  .  8036)
                       ("Gamma" .  8990)
                       ("Beta"  .  10052)
                       ("Alpha" .  12837)
                       ("Beta"  .  13634)
                       ("Beta"  .  14977)
                       ("Beta"  .  15719)
                       ("Alpha" .  17075)
                       ("Rho"   .  18949)
                       ("Gamma" .  21118)
                       ("Gamma" .  26923)
                       ("Alpha" .  31609))))
=> (("Alpha" . 4) ("Gamma" . 3) ("Rho" . 1) ("Beta" . 5))

Answer 10

感谢cl-incf对alist-get的支持：

;; (require 'cl-lib)
(defun simple-count (seq)
  "Count each unique element in SEQ."
  (let (counts)
    (dolist (element seq)
      (cl-incf (alist-get element counts 0 nil 'equal)))
    counts))

示例：

(let ((data '(("Alpha" .  1538)
              ("Beta"  .  8036)
              ("Gamma" .  8990)
              ("Beta"  .  10052)
              ("Alpha" .  12837)
              ("Beta"  .  13634)
              ("Beta"  .  14977)
              ("Beta"  .  15719)
              ("Alpha" .  17075)
              ("Rho"   .  18949)
              ("Gamma" .  21118)
              ("Gamma" .  26923)
              ("Alpha" .  31609))))
  (simple-count (mapcar 'car data)))
=> (("Rho" . 1) ("Gamma" . 3) ("Beta" . 5) ("Alpha" . 4))