方案“合并”功能实现

Question

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

这是我的尝试..。我觉得这应该是可行的，我只需检查每个列表中每个car的car，然后将这个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 34)(2 4)(2 3 4)(4)(2 3 4)(3 4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4)(4 TypeError:不能调用未定义的merge2、car、merge2、car、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)

Answer 2

您可能面临的部分问题是，作为一种函数式编程语言，Scheme是面向表达式的，而不是命令式的。所以，所有用编写的东西都有一个值，甚至是条件表达式。每件事都是一个表达式，为了产生一个结果而对其进行评估。如果您坚持纯函数式编程风格(方案鼓励，但不严格执行)，则会对表达式进行计算，以生成可以成为要计算的另一个表达式的一部分的结果。表达式只是简单的计算，它们不是导致计算机内存状态改变的过程；在函数式编程风格中没有副作用。因此，您应该从条件表达式的角度来考虑条件处理。

在命令式编程世界中，我能想到的最接近的对应对象是C或Java的?:操作符。您的函数从一系列条件表达式开始，但它们就像C或Java中没有分配给任何东西的一系列条件表达式，因此结果会被“丢弃”。

相反，开始思考:我们希望将两个列表合并在一起，如果其中一个是空的，那么合并两个列表又意味着什么呢？这为合并两个列表的迭代过程形成了一种“基本情况”或终止条件。

另外:如果两个列表都不是空的，合并在一起又意味着什么呢？如果我们可以根据现有列表(即归纳步骤)用较小的列表来表示解决方案，那么我们就可以开始了解递归过程可能是什么样子了。

因此，这一归纳步骤的部分解决方案将涉及某种表达式，它基于对每个列表的car进行检查，以确定哪一个列表应该放在列表合并的头上。如果(car a)小于或等于(car b)，那么(car a)可以成为(merge2 (cdr a) b)的第一个元素，对吗？当然，这假设有一种计算(merge (cdr a) b)的方法！

因此，听起来我们说的是一个条件表达式，它将成为更大定义或表达式的一部分，说明合并两个列表意味着什么：

(cond ((<= (car a) (car b)) (cons (car a) (merge2 (cdr a) b) ) )
       ...there's more to write here to finish the conditional expression )

我希望这有助于更清楚地说明Oscar Lopez是如何导出他的解决方案的；您可以看到，我上面开始编写的条件表达式也在他提供的函数中！

它的一个关键部分是从递归过程和递归定义的角度来思考。