loops - 使用 lisp 循环宏进行高级循环

Question

假设您有一个由列表组成的列表。例如，列表 A:(list '(1 2 3) '(1 4 3) )。此外，您将获得一个列表 B:'(0 2 3)。任务是:确定 A 的哪个子列表最匹配 B。注意这里匹配意味着列表相同位置的相同整数。所以对于这种情况，答案是子列表 '(1 2 3 )。如何使用 lisp 循环宏自动执行此操作？以下是我的尝试。

(defun select-most-specific-list (listA listB)
  (loop with candidate_sublist = '()
        for sublist in  listA
        do (loop for number1 in sublist
                 for number2 in listB
                 when (= number1 number2)
                 do (setq candidate_sublist sublist)
                 finally (return candidate_list))))

我给出以下输入:

(select-most-specific-list (list '(1 2 3) '(1 4 3) ) '(0 2 3))

我得到 NIL。 另外，我几乎可以肯定我的逻辑是错误的。对于上述输入，我希望它给出 '(1 4 3) 而不是正确答案 '(1 2 3)。这是因为仔细观察我的逻辑会发现我并没有存储所有比较的结果。所以最后一次成功的比较错误地指定了最具体的子列表。我怎样才能做到这一点？

Answer 1

问题

(loop for number1 in sublist
      for number2 in listB
      when (= number1 number2)
      do (setq candidate_sublist sublist)
      finally (return candidate_list))

一旦您的列表中有两个数字匹配，您就替换 candidate_sublist，即使它比之前的绑定(bind)更差。假设 candidate_sublist 是 (0 2 3)，它等于输入列表(没有比这更相似的了)。然后，您迭代下一个候选对象，即 (0 9 9)。使用您的代码，因为 (= 0 0)，您更改了 candidate_sublist。在做出决定之前，您确实必须检查要比较的两个列表中的所有值。

距离函数

您正在尝试定义列表之间的比较函数:如果一个列表与给定列表更相似，则它比另一个列表更好。这可以通过依赖距离函数来实现。 以下一个就足够了:

(defun distance (a b)
  (count nil (mapcar #'= a b)))

或者，用一个循环:

(defun distance (a b)
  (loop
     for aa in a
     for bb in b
     count (/= aa bb)))

因此，两个列表之间的差异越大，距离就越大。

部分订单

但是，此比较定义了偏序，因为您可以轻松地拥有两个与输入同样接近的列表。 例如，给定以下列表:

(0 1 2)

(1 1 2) 和 (0 1 1) 具有相同数量的匹配值。

您不能只返回一个最佳答案，否则您将根据任意标准(例如，实现细节，如列表的遍历顺序)选择一个答案。 我要做的是计算与输入列表距离相等的所有列表。

(defun closest-lists (list candidates)
  (loop
     for candidate in candidates
     for distance = (distance list candidate)
     for better = T then (< distance min-distance)
     for min-distance = (if better distance min-distance)
     for best-matches = (cond
                          (better (list candidate))
                          ((= distance min-distance) (cons candidate best-matches))
                          (t best-matches))
     finally (return (values best-matches min-distance))))

泛化

正如@Gwang-Jin Kim 在评论中所说，如果我们将 closest-lists 函数添加为参数，它甚至可以与其他距离函数一起使用。按照 sort 的命名约定，我们可以定义一个 predicate 参数来指定比较函数，以及一个 key 参数来指定如何检索要比较的值(分数)。那么，我们的函数其实就和列表没有关系了，可以改个更通用的名字:

(defun filter-by-score (candidates predicate &key (key #'identity))
  "Keep elements from CANDIDATES having the same best rank according to PREDICATE.

PREDICATE should return non-NIL if its first argument precedes its
second one. Elements are compared according the value returned by
applying KEY. The KEY function is guaranteed to be applied once only
for each element in CANDIDATES."
  (loop
     for candidate in candidates
     for score = (funcall key candidate)
     for better = T then (funcall predicate score best-score)
     for best-score = (if better score best-score)
     for best-items = (cond
                          (better (list candidate))
                          ((funcall predicate best-score score) best-items)
                          (t (cons candidate best-items)))
     finally (return (values best-items best-score))))

那么，我们之前的函数可以表示为:

(filter-by-score candidates #'< :key (lambda (u) (distance list u)))

但我们也可以这样做:

CL-USER> (filter-by-score '("a" "ab" "cd" "ed" "fe" "aaa" "bbb" "nnn") 
                          #'> :key #'length)
("nnn" "bbb" "aaa")
3

甚至:

CL-USER> (import 'alexandria:curry)
CL-USER> (ql:quickload :levenshtein)
CL-USER> (filter-by-score '("boat" "baobab" "brain" "biscuit")
                          #'<
                          :key (curry #'levenshtein:distance "ball"))
("brain" "boat")
3