我想用 Common Lisp 合并和排序两个排序列表

Question

我想用 Common Lisp 合并和排序两个已排序的关联列表。我做了代码。但是结果和我想的不一样

(defun MERGEALIST (K L)
  (cond ((and (eq nil K) (eq nil L)) nil)
        ((eq nil K) L)
        ((eq nil L) K)
        ((<= (car (car K)) (car (car L)))
         (cons K (MERGEALIST (cdr K) L)))
        ((> (car (car K)) (car (car L)))
         (cons L (MERGEALIST K (cdr L))))))

函数的输入K和L是排序的关联列表。例如，

K 是 ((1 . a) (3 . c) (5 . e))

L 是 ((2 . b) (4 . d)).

我预计结果是 ((1 . a) (2 . b) (3 . c) (4 . d) (5 . e))。

但结果完全不同。为什么会出现这个结果？谢谢。

Answer 1

你可以稍微简化一下。主要变化就像 jkiiski 的评论一样。

CL-USER 5 > (defun MERGEALIST (K L)
              (cond ((and (null K) (null L)) nil)
                    ((null K) L)
                    ((null L) K)
                    ((<= (caar K) (caar L))
                     (cons (car K) (MERGEALIST (cdr K) L)))
                    ((> (caar K) (caar L))
                     (cons (car L) (MERGEALIST K (cdr L))))))
MERGEALIST

CL-USER 6 > (mergealist '((1 . a) (3 . c) (5 . e)) '((2 . b) (4 . d)))
((1 . A) (2 . B) (3 . C) (4 . D) (5 . E))

内置函数 merge 可以做到：

CL-USER 9 > (merge 'list
                   '((1 . a) (3 . c) (5 . e))
                   '((2 . b) (4 . d))
                   #'<
                   :key #'car)
((1 . A) (2 . B) (3 . C) (4 . D) (5 . E))

Answer 2

(cons K (MERGEALIST (cdr K) L))

这里你把 complete 列表 K 放在你计算的 "rest" 前面。您只需要它的第一个元素（您刚刚测试 "come before" L 的第一个元素）：

(cons (car K) (MERGEALIST (cdr K) L))

不过请注意，您可以将其简化很多：

(defun merge-alists (k l)
  (cond 
    ;; Common case first, if both alists are not empty, then select
    ;; the first element of that alist, whose car is less. Then, recurse.
    ((and (consp k) (consp l))
         (if (<= (caar k) (caar l))
           (cons (car k) (merge-alists (cdr k) l))
           (cons (car l) (merge-alists k (cdr l)))))
    ;; One of the alists is empty, use either the not-empty one or ...
    ((consp k) k)
    ;; ... just the other (when k is empty or both are empty)
    (t l)))

（最后两个 cond 子句可以简化为 (t (or k l)) ......但这样可能有点太简洁了，无法清楚地理解。）

或者，如前所述，使用 merge。

我想用 Common Lisp 合并和排序两个排序列表

I want to merge and sort two sorted lists with Common Lisp

lisp

common-lisp