我刚开始学习球拍,所以我仍在努力弄清楚这门语言的复杂性。我正在尝试在列表中实现自己的搜索功能。如果函数找到它,它将返回索引,否则返回 -1。
(define (find-index list item)
(if (equal? (length list) 1)
(if (equal? (first list) item) 0 1)
(if (equal? (first list) item)
0
(+ 1 (my-search (rest list) item)))))
因此,find-index 函数是一个递归函数,它在列表中遍历以查找等效于"item"的项目。我写了它,如果列表中有 4 个元素,该函数可以返回 0-4 之间的任何数字。
(define (my-search list item)
(define length (my-length list))
(define index (find-index list item))
(if (= index length) -1 index))
我的想法是,如果 find-index 函数返回一个等于列表长度的数字,则意味着该函数没有找到该项目,因此 my-search 函数应该返回 -1。
但是,当我投入时
(my-search (list "apple" "barbecue" "child" "demon" "enter") "fire")
我得到的结果是 3,而不是 -1。如果我在 if 语句之前打印索引,索引是 3 而不是 5。如果
(if (= index length) -1 index))
不是我的搜索功能的一部分,那么一切都很好。
我认为正在发生的事情是索引是函数本身的 id,而不是函数的结果。但是,我不明白为什么这会影响我的搜索的返回结果。有人愿意阐明这个问题吗?
此外,欢迎任何风格批评。我想知道我是否不遵守惯例。
奇怪的行为是由find-index
调用my-search
调用find-index
(相互递归!在某些时候,这种额外的if
会导致递归过早结束。解决方案:在find-index
过程中将调用my-search
替换为find-index
。
现在这个问题已经解决了,我们可以编写一个过程来在列表中查找元素的索引或发出未找到元素的信号,如下所示:
(define (find-index lst item)
(cond ((empty? lst) #f)
((equal? (first lst) item) 0)
(else
(let ((result (find-index (rest lst) item)))
(if result (add1 result) #f)))))
让我们看看上述内容如何改进您的程序:
- 构建具有多个条件的过程的首选方法是使用
cond
- 不应使用
list
作为参数名称,它与具有相同名称的内置过程冲突 - 出于同样的原因,不应
length
调用本地定义 - 使用
length
来检查我们是否跳出列表并不是一个好主意,构建良好的递归将解决这个问题,而不必再次迭代列表 - 通常使用
#f
来指示搜索过程未找到要查找的内容 - 在对列表的结构良好的递归中,您应该检查列表是否为空,通常这是我们编写的第一个基本情况 - 如果传递空列表,您的过程将失败
- 我们使用
let
来声明局部变量,在这种情况下是有意义的,以避免两次调用递归 - 使用
(add1 x)
,它比(+ 1 x)
更惯用
但是等等,我们可以做得更好!上述解决方案可以用尾递归风格重写;通过确保递归调用是我们做的最后一件事,我们的过程将使用常量空间,并且它将与传统编程语言中的循环一样高效。诀窍是传递一个额外的参数,其中包含要返回的值(在本例中为索引(。为简洁起见,我将使用命名let
:
(define (find-index lst item)
(let loop ((lst lst) (idx 0))
(cond ((empty? lst) #f)
((equal? (first lst) item) idx)
(else (loop (rest lst) (add1 idx))))))
您可以验证这两个过程是否按播发工作:
(find-index (list "apple" "barbecue" "child" "demon" "enter") "fire")
=> #f
(find-index (list "apple" "barbecue" "child" "demon" "enter") "child")
=> 2
这就是我解决问题的方式。
(define (find-index L item) ; L your list. item the item for which you want the index
(define (aux L res) ; Auxiliary function. L your list. item the item for which you want the index
(cond ((null? L) -1) ; No thing was found, return -1.
((eq? (car L) item) res) ; If the item is equal to the current item then return the position.
(else (aux (cdr L) (add1 res))))) ; Move on to the next item in the list and increment the position.
(aux L 0)) ; Call of the auxiliary function that will be doing the job
试运转。。。
(define L '(a b c d))
元素不在列表中
(find-index L 'e)
输出 : -1
元素"d">
(find-index L 'd)
输出 : 3
下面是尝试使用与原始示例相同的样式的find-index
版本。我使用xs
而不是list
(这是"xes列表"的缩写(。
请注意,最好使用 false 值#f
来指示"未找到"。
(define (find-index xs item)
(if (empty? xs)
-1 ; not found
(if (equal? (first xs) item)
0 ; found at beginning
(let ([index-in-rest (find-index (rest xs) item)]) ; index in rest of list
(if (= index-in-rest -1)
-1 ; not found in rest of list
(+ 1 index-in-rest)))))) ; add 1 because we skipped
the first element