recursion - 复制长度函数的有效方法

Question

我正在复制 Racket 的长度函数，仅使用 car 和 cdr 来比较两个列表的长度并返回两个列表中较短的一个。

长度函数简单来说就是:

(define length
 (lambda (list)
    (if (null? list)
        0
        (+ 1 (length (cdr list))))))

以及用于比较两个列表时

(define short
  (lambda (list1 list2)
    (if (<= (length list1) (length list2))
        list1
        list2)))

> (short '(a b c) '(1 2 3 4 5 6 7))

将返回“(a b c)”。

但是，此方法无效，尤其是当一个列表比另一个列表长得多时，因为它会在返回较短的列表之前迭代两个列表。

下面我有一个更有效的方法。然而我想知道是否有一种更有效/替代的方法来获得更短的长度而不检查两个列表的末尾。也许通过与 car/cdr 同时递归地遍历列表，直到较短的列表首先到达其末尾。

(define shorter?
  (lambda (list1 list2)
    (and (not (null? list2))
         (or (null? list1)
             (shorter? (cdr list1) (cdr list2)))))) 

(define shorter
  (lambda (list1 list2)
    (if (shorter? list2 list1)
        list2
        list1)))

Answer 1

您的更短？过程已经尽可能高效 - and和or特殊形式short -电路，当任何计算表达式的值为 true (对于 or 特殊形式)或 false (对于 code> 和 特殊形式)。因此，一旦其中一个列表达到 null，递归就会停止。您的 shorter? 实现相当于，并且与此一样高效:

(define shorter?
  (lambda (list1 list2)
    (cond ((null? list2) #f)
          ((null? list1) #t)
          (else (shorter? (cdr list1) (cdr list2))))))

如果您想要一个更紧凑的解决方案，您可以使用命名的 let (如另一个答案中所示)或内部帮助程序将两个过程放入一个过程中，两者是等效的。我将演示后面的方法:

(define (shorter lst1 lst2)
  (define (shorter-list list1 list2)
    (cond ((null? list2) lst2)
          ((null? list1) lst1)
          (else (shorter-list (cdr list1) (cdr list2)))))
  (shorter-list lst1 lst2))