lisp - 在 r5rs 方案中实现长度（dracket）

Question

是否可以使用 car 和 cdr 系列函数来实现 R5RS 方案函数“长度”？如果是这样，有人可以发布实现吗？

谢谢，

Answer 1

当然，这很简单。我没有给出直接的答案，因为这看起来像家庭作业，而且写起来很简单。填空：

(define (length lst)
  (if <???>              ; if the list is empty
      <???>              ; return 0
      (<???>             ; otherwise add 1 and
       (length <???>)))) ; advance the recursion over the rest of the list

请注意，只cdr使用了。我们对列表的实际内容不感兴趣，因此可以忽略car.

Answer 2

Óscar López 的回答是正确的。这里还有两个实现（同样是填空）。

第一个是左折叠解决方案（与 Óscar 的解决方案相反，后者是右折叠解决方案）：

(define (length lst)
  (let loop ((lst lst)
             (count 0))
    (if <???>                   ; if the list is empty
        <???>                   ; return the count
        (loop <???> <???>))))   ; otherwise bump the count and continue down the list

这具有尾递归的优点，而右折叠版本不是。

第二种是龟兔赛跑解决方案，它允许检测循环列表（如果给定循环列表，早期的解决方案将永远运行）：

(define (length lst)
  (if (null? lst)
      0
      (let loop ((tortoise lst)
                 (hare (cdr lst))
                 (count 1))
        (cond ((eq? tortoise hare) #f)                   ; found a cycle
              ((null? hare) <???>)                       ; reached end of list
              ((null? (cdr hare)) <???>)                 ; reached end of list too
              (else (loop <???> <???> (+ count 2)))))))  ; bump the count and keep looking