这里是我系统化制作一个用于查找列表长度的函数的方法。
最终结果将会是:
(define (length lst)
(cond
[(empty? lst) 0]
[(cons? lst) (+ 1 (length (rest lst)))]))
但更重要的是系统性的过程,你可以使用它来编写更多的程序。我在这里使用的过程是书籍
How to Design Programs 中解释的
设计配方。
1:什么是列表?
列表要么是空的,要么是第一个元素与其余元素的组合。这个“剩余”是另一个列表。
在Racket中,“空”写作'()
,列表的“组合”写作cons
。
A [Listof Element] is one of:
- '()
- (cons Element [Listof Element])
一些列表的示例:
'()
(cons "I'm alone" '())
(cons "Hello" (cons "there" '()))
(cons 1 (cons 3 (cons 5 (cons 7 (cons 9 '())))))
2:什么是length
函数?
length
函数接受一个列表,并生成一个代表列表中元素数量的数字。空列表的长度为0
,上面的示例应该具有长度0
,1
,2
和5
。
(define (length lst)
???)
3:定义中的案例是什么?
列表要么为空,要么是cons。为了测试它是否为空,我们可以使用一个cond
,其中问题(empty? lst)
用于空情况,而问题(cons? lst)
用于cons情况。
(define (length lst)
(cond
[(empty? lst) ???]
[(cons? lst) ???]))
4:每种情况下有哪些数据的"子部分"可用?
一个空列表没有任何子部分。
然而,(cons Element [Listof Element])
有两个子部分:
- 第一件事,
Element
,
- 和列表的其余部分,
[Listof Element]
。
在Racket中,您可以使用first
和rest
来获取它们。
(define (length lst)
(cond
[(empty? lst) ???]
[(cons? lst) ... (first lst) ... (rest lst) ...]))
5: 这些子部分中是否有复杂的数据?
(first lst)
只是一个Element
。就长度而言,它不是复杂的,我们不需要进一步处理它。
(rest lst)
是另一个[Listof Element]
,因此它是复杂的。我们如何处理它?通过使用一个辅助函数。
在这种情况下,我们需要一个与长度相关的辅助函数,并将[Listof Element]
作为参数。在这种情况下,该辅助函数恰好是正在定义的函数length
!我们可以在(rest lst)
上递归使用它,因为它是一个较小的子部分。
(define (length lst)
(cond
[(empty? lst) ???]
[(cons? lst) ... (first lst) ... (length (rest lst)) ...]))
6:使用您对长度的直觉和我们之前编写的示例填补空缺
第一个示例 (length '()) = 0
告诉我们第一个 ???
空缺应该用 0
填充。
(define (length lst)
(cond
[(empty? lst) 0]
[(cons? lst) ... (first lst) ... (length (rest lst)) ...]))
第二个难点是处理第一个元素和剩余元素的长度。但是你对长度的直觉应该告诉你,合并后的列表的长度应该是剩余部分的长度加一。将其转化为代码如下:
(define (length lst)
(cond
[(empty? lst) 0]
[(cons? lst) (+ 1 (length (rest lst)))]))
我使用的系统化步骤在书籍
如何设计程序中有详细解释。