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

Question

在此处堆叠溢出的新成员。我正在尝试找到方案中所有元素的所有事件的索引，但是我不确定如何将代码推进以下内容 - 打印第一次发生 - 也许有人可以帮助：

(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

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

在方案中，这通常是由命名let的递归完成的。在每次迭代中，您都有一个索引变量i，结果列表r和其余的输入列表L，在每个迭代步骤中变小。

可以简化示例的if子句。

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

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

当L为null时，您已经到达输入列表的末尾。在这种情况下，返回结果列表。您必须扭转结果列表，因为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))))))

btw：方案在静态上键入C或Java。这意味着您不需要在保留变量值中编码错误，因为它在-1中完成。在方案中，您返回false #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

第一个观察结果是，要返回 all 解决方案，函数应返回索引列表。如果找不到元素，则应返回空列表。

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

第三，我们需要额外的论点来跟踪当前位置。

(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)