DrRacket : How to get the position of a value in a list

Question

I am trying to get a list of positions of a value in a list in Intermediate Student Language.

For instance I wish a list of positions for value "A" in the following list

(list false A false false false false A false false false )

The output must be something like

(list 1 6)

Answer 1

Well there are a few things we can quickly understand, the first is that you're going to need to recurse through your initial list, and the second is that you're going to need to keep an accumulator list, and somehow have a notion of what element of the first list you're looking at, so we can also add a counter.

So,

; listsearch : (listof Any) Any -> (listof Int)
;   Searches a list for val and returns a list of indexes for occurrences of val in lst
;   (listsearch '(1 2 1 3 4 1) 1) => '(0 2 5)
(define (listsearch lst val) 
  (local [(define (helper lst acc counter)
            (cond [(empty? lst)             acc]
                  [(equal? val (first lst)) (helper (rest lst) 
                                                    (cons counter acc)
                                                    (add1 counter))]
                  [else                     (helper (rest lst) acc (add1 counter))]))]
    (reverse (helper lst empty 0))))

I've added a local because the counter should be present, but we want the actual function to be tidy, so the call is simply requiring a list and a value.

This simply goes through the list one by one, and makes three checks

• Is the list empty? Return my accumulated list (base is empty)
• Is the first item in the list my value? Start again but add that value to my accumulator and add one to my counter
• Is the first item in the list something else? Start again but add one to my counter

This results in a backwards list, so we reverse it at the end.

That's it! :)

Answer 2

I'll give you some hints to solve this problem, it's much better if you reach a solution by your own means. Fill-in the blanks:

; position procedure
;    lst: input list
;    ele: the searched element
;    idx: initial index, starts in 0
(define (position lst ele idx)
  (cond (<???>       ; if the input list is empty
         <???>)      ; then we're done, return the empty list
        (<???>       ; if the current element equals the one we're looking then
         (cons <???> ; build output list, cons the index where we found it
               (position <???> ele <???>))) ; and advance the recursion
        (else                               ; otherwise
         (position <???> ele <???>))))      ; just advance the recursion

Notice that the idx parameter is necessary to keep track of the index we're currently over, starting at zero. When the recursion advances, you must advance both the input list and the index. Don't forget to test the procedure:

(position '(false A false false false false A false false false) 'A 0)
=> '(1 6)