CODEWITHSUNDEEP
scheme
Gavin Coll
Gavin Coll

Reputation: 19

Scheme - Finding all indexes of occurrences of a list element

new member to Stack Overflow here. I'm trying to find the indices of all occurrences of an element in Scheme but I'm not sure how to advance my code past the following - printing the first occurrence - maybe someone could please help:

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

Upvotes: 1

Views: 1333

Answers (4)

soegaard
soegaard

Reputation: 31145

The first observations is that to return all solutions the function should return a list of the indices. If an element is not found, then it should return the empty list.

The second observation is that, whether or not the element is found the search should continue in the rest of the list.

Third we need an extra argument to keep track of the current position.

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

Upvotes: 2

rnso
rnso

Reputation: 24623

Adding to answer by @ceving , cond can also be used in loops and may make the code clearer: 

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

Upvotes: 2

ceving
ceving

Reputation: 23881

Your code does not use any kind of loop. In order to get all occurrences you have to iterate somehow.

In Scheme this is done typically by recursion with a named let. During each iteration you have an index variable i, the result list r and the remaining input list L, which gets smaller during each iteration step.

The if clause of your example can be simplified.

If you find the value in the first element of the list, then increment the index, append the current index to the result list and continue with the rest of the input list.

If you do not have a match, than increment the index, but do not add the index to the result list and continue also with the remaining input list.

You have reached the end of the input list when L is null. In that case return the result list. You have to reverse the result list, because cons appends at the beginning.

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

You can avoid typing the loop command twice by putting the if clause into the argument of the loop.

(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 is not statically typed as C or Java. This means you do not need to encode errors in reserved variable values as it is done in C with -1. In Scheme you return either false #f or an empty list '() or you throw an error with (error "Sorry").

Upvotes: 2

Sylwester
Sylwester

Reputation: 48775

You need a helper to hold the extra variables such as the current index you are examining:

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

Note that (define (a args ...) body ...) is the same as (define a (lambda (args ...) body ...)).

Upvotes: 2

Related Questions