是否可以使用 car 和 cdr 系列函数来实现 R5RS 方案函数“长度”?如果是这样,有人可以发布实现吗?
谢谢,
当然,这很简单。我没有给出直接的答案,因为这看起来像家庭作业,而且写起来很简单。填空:
(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
.
Ó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