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)