スキーム - リスト要素の出現のすべてのインデックスを見つける

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 (a args ...) body ...)が(define a (lambda (args ...) body ...))と同じであることを

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

注：このようご検討されている現在のインデックスとして余分な変数を保持するためにヘルパーを必要としています。

Answer 2

コードではループを使用していません。すべての出現を取得するには、何とか反復する必要があります。

これは、通常、再帰によってnamed 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句を入れることで、loopコマンドを2回入力することを避けることができます。

(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：SchemeはCまたはJavaとして静的に型指定されていません。これは、-1でCで行われるように、予約された変数値のエラーをエンコードする必要がないことを意味します。 Schemeでは、偽#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

最初の観察は、関数がのリストを返すべき全て解を返すことですインデックス。要素が見つからない場合は、空のリストを返す必要があります。

第2の観察は、要素が見つかったかどうかにかかわらず、検索は残りのリストで続行する必要があるということです。

第3に、現在の位置を追跡するために追加の引数が必要です。

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