Common Lisp 中的 assoc 函数和 2 个问题

Question

我有一个列表，其中包含一个句子中出现的字母：

(setf mylist '((a 1) (b 2) (a 1) (b 1) (o 2) (m 1))) ; "abba boom"

我想关联所有具有例如字母 b 的对：

(assoc 'b mylist) ; => returns just the first occurance of b: (B 2)

如何获取与b关联的所有对并列出它们？例如

(my-assoc 'b mylist) ; => ((B 2) (B 1))

2- 如何编写一个函数，将字母与它们出现的总和一起分组？例如

(my-group-sum mylist) ; => ((A 2) (B 3) (O 2) (M 1))

这是我的看法，假设如上所述 my-assoc 存在：

(defun my-group-sum (lst) 
  (loop for (letter num) in lst do 
     (let ((temp (my-assoc letter lst)) 
           (occurance 0)) 
          (dolist (pair temp) 
             (incf occurance (cdr pair)))); cdr should be "second" 
          collect (letter occurance)))

注意：此代码未经编译，也未经测试。即使 my-assoc 函数可用，也很可能出错。这只是为了演示目的。

Answer 1

让我们使用相同的示例，我使用 defvar 来正确声明变量：

(defvar *list* '((a 1) (b 2) (a 1) (b 1) (o 2) (m 1)))

How to get all pairs associated with b and list them?

Common Lisp 定义 REMOVE，它构建了一个删除了一些元素的新列表。有时您想要的恰恰相反，一个只保留某些元素的函数。为此，您必须采用补码功能。例如：

(remove 'a *list* :test-not #'eq :key #'car)
=> ((A 1) (A 1))

上面的意思是我们删除了元素 x 使得 (eq 'a x) 是 false，因为 :test-not 参数。 :key 参数表示我们通过第一个元素比较条目。

你可以自己循环：

(loop 
  for entry in *list* 
  when (eq (car entry) 'a)
    collect entry)

How to write a function which will group the letters along with the sum of their occurances?

您提供了一些尝试，这里是格式化的：

(defun my-group-sum (lst)
  (loop
     for (letter num) in lst
     do (let ((temp (my-assoc letter lst)) (occurance 0))
          (dolist (pair temp)
            (incf occurance (cdr pair))))
     collect (letter occurance)))

有些事情不太好，如果你在实时环境中测试这段代码，你应该在编译函数时（如果你的 Lisp 编译代码）或者运行中的代码时出现错误一个测试。让我们回顾一些问题：

occurance 拼写为 occurrence（一个小问题，但有助于检查）
(letter occurance) 不是你构建列表的方式，你应该调用 (list letter occurance) 否则它意味着：调用函数 letter 参数 occurance，尽管这里（可能）没有定义这样的 letter 函数，并且因为你想要 return 一个包含两个元素的列表。
当您尝试构建 (list letter occurance) 时，符号 occurance 未绑定在词法范围内。它绑定在 do 循环表达式中的 let 内，但在这里您在该范围之外使用它。最好直接调用collect：

这是修改后的版本：

(defun my-group-sum (lst)
  (loop 
     for (letter num) in lst
     collect (let ((temp (remove letter lst :test-not #'eql :key #'car)) 
                   (occurance 0))
               (dolist (pair temp)
                 (incf occurance (cdr pair)))
               (list letter occurance))))

let return 中的最后一个表格是收集的结果。

现在，如果你测试你的代码，你会发现有一个问题：lst 未被调用 remove 修改（它构建了一个新列表），这意味着您可能会在主循环中找到其他匹配项。例如，一开始你有：

((a 1) (b 1) (a 1))

循环的第一次迭代收集 (a 2)，但随后在 ((b 1) (a 1)) 上进行剩余迭代，其中仍然包含 a。

另一种方法是改变绑定 lst 或改变列表。我不确定如果您更改在 loop 中迭代的列表，并且根据 3.6 遍历规则和副作用，标准禁止变异，我不确定所有实现是否都反应良好 .

迭代更改值的常用方法是：

(loop for var = <init> then <next>)

... when 后面的是下一个要使用的列表。您可以使您的算法适应 return 您从中删除项目的列表。

但第一种方法是分而治之：

写一个函数 aggregate-step 接受一个列表和 return 列表中的两个值：(1) 一个累积的条目，它是 nil 或一个形式 (name count) 和 (2) 要使用的下一个列表。
编写调用它的定点循环。假设您使用 (list entry rest) 到 return 这两个值，并且 entry 可能是 nil，这是循环的样子：
```
(loop 
  for curlist = lst then rest
  for (entry rest) = (aggregate-step curlist)
  while entry
    collect entry)
```

Answer 2

为了完成@coredump 出色而详细的回答，我想提一个不同的（更有效的）方法来解决问题中提出的“分组依据”问题。

这种方法只是简单地扫描列表一次来执行操作，使用哈希 table 来收集总和：

CL-USER> (defun my-group-sum (lst)
           (let ((table (make-hash-table)))
             (loop for (letter num) in lst
                   do (incf (gethash letter table 0) num))
             (loop for key being the hash-key of table
                   using (hash-value val)
                   collect (list key val))))
MY-GROUP-SUM
CL-USER> (my-group-sum '((a 1) (b 2) (a 1) (b 1) (o 2) (m 1)))
((B 3) (M 1) (O 2) (A 2))

在第一个循环 (gethash letter table 0) 中，如果 table 中不存在 letter，则为其创建一个值为 0 的条目，或者 [=25] =] letter 的当前值，incf 通过添加当前数字来递增它。

第二个循环简单地收集结果。当然，如果您需要以某种方式对其进行排序，则需要添加对 sort.

的显式调用

Common Lisp 中的 assoc 函数和 2 个问题

assoc function in Common Lisp and 2 questions

lisp

common-lisp