如果在列表中找不到该数字，如何 return false

Question

所以，我正在尝试解决这个硬件问题：编写一个函数，它接受两个参数，一个列表和一个数字，函数 returns 中最左边出现的数字的索引列表。例如：

如果'(1 2 3 3 4)和num = 3，则returns 2
如果'(3 2 3 3 4)和num = 3，则returns 0

我可以完成那部分，但如果找不到号码怎么办？如果在列表中找不到 num 时我想 return false 怎么办？我该怎么做？

请记住，我正在尝试以适当的递归而不是尾递归来执行此操作。

这是我的代码。

(define (first_elt_occ lst num)
   (cond
       ((null? lst) #f)
       ((eq? (car lst) num) 0)
       (else
          (+ 1 (first_elt_occ (cdr lst) num)))))

(first_elt_occ '(1 2 3 3 4) 3) ;2
(first_elt_occ '(3 2 3 3 4) 3) ;0
(first_elt_occ '(1 2 5 4 3) 3) ;4
(first_elt_occ '(1 2 5 4 3) 6) ;Error 
     ;(makes sense because you can't add boolean expression)

我的另一个问题是，如果我被要求 return 列表中 最右边 出现的数字的索引，我将如何解决这个问题（适当的递归）。例如：'(3 4 5 4 3 7 ), num = 3 returns 4.

谢谢！

Answer 1

正如评论中所建议的那样，如果我们使用尾递归来实现该过程，这会更容易 - 顺便说一下，尾递归是 “正确的递归”，你怎么想的不然呢？

通过定义一个名为 loop 的辅助过程并将累积结果传递给参数，我们可以 return #f 或元素的索引：

(define (first_elt_occ lst num)
  (let loop ((lst lst) (acc 0))
    (cond
      ((null? lst) #f)
      ((equal? (car lst) num) acc)
      (else (loop (cdr lst) (add1 acc))))))

如果，对于某些奇怪的要求，您不能在您的解决方案中使用尾递归，则可以重写您的原始解决方案以解决答案为 #f 的情况 - 但这并非如此优雅或高效：

(define (first_elt_occ lst num)
  (cond
    ((null? lst) #f)
    ((equal? (car lst) num) 0)
    (else
     (let ((result (first_elt_occ (cdr lst) num)))
       (if (not result) #f (add1 result))))))

无论哪种方式，它都按预期工作：

(first_elt_occ '(1 2 3 3 4) 3) ; 2
(first_elt_occ '(3 2 3 3 4) 3) ; 0
(first_elt_occ '(1 2 5 4 3) 3) ; 4
(first_elt_occ '(1 2 5 4 3) 6) ; #f

Answer 2

不清楚您为什么反对尾递归。你谈论“适当的递归”，这不是任何人使用的技术术语，但我假设你的意思是非尾递归：递归过程而不是迭代过程，在 SICP 术语中。请放心，尾递归是非常合适的，并且通常比非尾递归更可取，前提是不必进行其他权衡以启用尾递归。

正如 Óscar López 所说，使用尾递归解决这个问题确实更容易。但是如果你坚持的话，肯定是可以硬着头皮解决的。您必须避免盲目地将结果加 1：相反，检查它，如果它是一个数字则加 1，或者如果它是假则原样返回。例如，参见 number? 谓词。

Answer 3

我不建议实际采用这种方法，因为正常的尾递归实现更有效、更简单且更容易理解，但您可以使用延续来短路展开调用堆栈失败案例：

(define (first_elt_occ lst num)
  (call/cc
   (lambda (return)
     (letrec ((loop (lambda (lst)
                      (cond
                       ((null? lst) (return #f))
                       ((= (car lst) num) 0)
                       (else (+ 1 (loop (cdr lst))))))))
        (loop lst)))))

Answer 4

基本的找到第一次出现"skeleton" function是

(define (first_elt_occ lst num)
   (and (not (null? lst))
        (or (equal (car lst) num)
            (first_elt_occ (cdr lst) num))))

这不是 return 索引。如何添加进去？

(define (first_elt_occ lst num)
   (and (not (null? lst))
        (or (and (equal (car lst) num) 0)
            (+ 1 (first_elt_occ (cdr lst) num)))))

有用吗？如果该元素不存在，则不会！那时它会导致错误。如何解决？改+，原来如此！

(define (first_elt_occ lst num)
  (let ((+ (lambda (a b) (if b (+ a b) b))))
    (and (not (null? lst))
         (or (and (= (car lst) num) 0)
             (+ 1 (first_elt_occ (cdr lst) num))))))

现在它按预期工作了：

> (first_elt_occ '(1 2 3 3 4) 3)
2
> (first_elt_occ '(3 2 3 3 4) 3)
0
> (first_elt_occ '(3 2 3 3 4) 5)
#f

为了获得您想要的第二个功能，我们将其稍微重组为

(define (first_elt_occ lst num)
  (let ((+ (lambda (a b) ...... )))
    (and (not (null? lst))
         (+ (and (= (car lst) num) 0)
            (first_elt_occ (cdr lst) num)))))

现在，新 + 应该是什么？你能完成这个吗？很简单！

如果在列表中找不到该数字，如何 return false

How to return false if the number is not found in the list

lisp

recursion

scheme

functional-programming

racket