Scheme - 查找列表元素出现的所有索引

Question

这里是Stack Overflow的新成员。我试图找到计划元素的所有事件的索引，但我不知道如何提高自己过去的代码如下 - 打印中第一次出现 - 也许有人能帮：

(define positions 
    (lambda (A L) 
    (if (null? L) 
     -1 
     (if (eq? (car L) A) 
      0 
      (if (= (positions A (cdr L)) -1) 
       -1 
       (+ 1 (positions A (cdr L)))))))) 

Answer 1

你需要一个帮手，以存放额外的变量，如您检查当前指数：

(define (positions needle haystack) 
    (define (helper index haystack result) 
    (cond (<haystack empty> result) 
      (<first element matches needle> 
      <recurse increment index, cdr haystack and cons index to result>) 
      (else <recurse increment index, cdr haystack, same result>))) 
    (helper 0 haystack '())) 

注意(define (a args ...) body ...)相同(define a (lambda (args ...) body ...))。

Answer 2

您的代码不使用任何类型的循环。为了获得所有的事件，你必须以某种方式迭代。

在方案中，这通常通过递归使用named let来完成。在每次迭代期间，您都有一个索引变量i，结果列表r和其余输入列表L，在每个迭代步骤中该列表变小。

您示例中的if子句可以简化。

如果您在列表的第一个元素中找到值，则增加索引，将当前索引附加到结果列表并继续输入列表的其余部分。

如果您没有匹配，那么请增加索引，但不要将索引添加到结果列表中，并继续使用剩余的输入列表。

当L为空时，您已到达输入列表的末尾。在这种情况下返回结果列表。您必须翻转结果列表，因为cons会在开始处追加。

(define positions 
    (lambda (A L) 
    (let loop ((i 0) 
       (r '()) 
       (L L)) 
     (if (null? L) 
      (reverse r) 
      (if (eq? (car L) A) 
       (loop (+ i 1) (cons i r) (cdr L)) 
       (loop (+ i 1) r (cdr L))))))) 

通过将if子句放入循环的参数中，可以避免输入两次循环命令。

(define positions 
    (lambda (A L) 
    (let loop ((i 0) 
       (r '()) 
       (L L)) 
     (if (null? L) 
      (reverse r) 
      (loop (+ i 1) 
       (if (eq? (car L) A) 
        (cons i r) 
        r) 
       (cdr L)))))) 

顺便说一句：Scheme不是静态类型为C或Java。这意味着您不需要在保留变量值中编码错误，因为它在C中用-1完成。在计划中，您返回假#f或空列表'()或者您输入(error "Sorry")错误。

Answer 3

添加由@ceving回答，cond也可以循环使用，并且可以使代码更清晰：

(define (positions A L) 
    (let loop ((i 0) 
      (r '()) 
      (L L)) 
    (cond 
     [(null? L) 
     (reverse r)] 
     [(eq? (car L) A) 
     (loop (+ i 1) (cons i r) (cdr L))] 
     [else 
     (loop (+ i 1) r (cdr L))] 
    ))) 

Answer 4

首先观察的是，返回所有解决方案的功能应该返回列表指数。如果找不到元素，则应返回空列表。

第二个观察结果是，无论是否找到该元素，搜索应该继续在列表的其余部分。

第三，我们需要一个额外的参数来跟踪当前位置。

(define positions 
    (lambda (A L i) 
    (if (null? L) 
     '()          ; not found 
     (if (equal? (car L) A) 
      (cons i        ; found at index i 
        (positions A (cdr L) (+ i 1))) ; and continue 
      (positions A (cdr L) (+ i 1))))))  ; not found, continue 

> (positions 'a '(a b a c a d) 0) 
'(0 2 4)