方案 "Merge"函数实现

Question

我正在尝试使用Scheme 创建一个Merge2 函数，该函数接受2 个有序列表并将它们组合成一个有序列表。例如 (merge2 '(1 3 4) '(2 4 5)) 将产生 (1 2 3 4 4 5)

这是我的尝试..我觉得这应该可行，我只需检查每个列表中每个 car 的 min ，然后附加此 min 到 merge2 的递归调用。那么我的基本情况是当其中一个列表变空时，它应该只返回要附加的另一个列表。

(define (merge2 a b)
    (if (and (null? a) (null? b))
        `())
    (if (null? a) b)
    (if (null? b) a)

    (display a)
    (display b)

    (if (= (min (car a) (car b)) (car a)) 
        (append (list (min (car a) (car b))) (merge2 (cdr a) b)))

    (if (= (min (car a) (car b)) (car b)) 
        (append (list (min (car a) (car b))) (merge2 a (cdr b))))) 

输出:

(1 2 4)(2 3 4)(2 4)(2 3 4)(4)(2 3 4)(4)(3 4)(4)(4)()(4)
TypeError: Cannot call method 'apply' of undefined [merge2, merge2, merge2, merge2, merge2, merge2, car, merge2, merge2, merge2, merge2, merge2, merge2, car, merge2, merge2, merge2, merge2, merge2, merge2, car]

Answer 1

解决方案更简单，利用两个列表都已排序的事实，从一个列表中选择一个元素，然后根据较大的元素前进，直到其中一个列表结束。这就是我的意思:

(define (merge lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        ((>= (car lst1) (car lst2))
         (cons (car lst2) (merge lst1 (cdr lst2))))
        (else
         (cons (car lst1) (merge (cdr lst1) lst2)))))

它按预期工作:

(merge '(1 3 4) '(2 4 5))
=> '(1 2 3 4 4 5)