How do I find the index of an element in a list in Racket?

Question

This is trivial implement of course, but I feel there is certainly something built in to Racket that does this. Am I correct in that intuition, and if so, what is the function?

Solution 1

Strangely, there isn't a built-in procedure in Racket for finding the 0-based index of an element in a list (the opposite procedure does exist, it's called list-ref). However, it's not hard to implement efficiently:

(define (index-of lst ele)
  (let loop ((lst lst)
             (idx 0))
    (cond ((empty? lst) #f)
          ((equal? (first lst) ele) idx)
          (else (loop (rest lst) (add1 idx))))))

But there is a similar procedure in srfi/1, it's called list-index and you can get the desired effect by passing the right parameters:

(require srfi/1)

(list-index (curry equal? 3) '(1 2 3 4 5))
=> 2

(list-index (curry equal? 6) '(1 2 3 4 5))
=> #f

UPDATE

As of Racket 6.7, index-of is now part of the standard library. Enjoy!

Solution 2

Here's a very simple implementation:

(define (index-of l x)
  (for/or ([y l] [i (in-naturals)] #:when (equal? x y)) i))

And yes, something like this should be added to the standard library, but it's just a little tricky to do so nobody got there yet.

Note, however, that it's a feature that is very rarely useful -- since lists are usually taken as a sequence that is deconstructed using only the first/rest idiom rather than directly accessing elements. More than that, if you have a use for it and you're a newbie, then my first guess will be that you're misusing lists. Given that, the addition of such a function is likely to trip such newbies by making it more accessible. (But it will still be added, eventually.)

Solution 3

One can also use a built-in function 'member' which gives a sublist starting with the required item or #f if item does not exist in the list. Following compares the lengths of original list and the sublist returned by member:

(define (indexof n l)
  (define sl (member n l))
  (if sl 
      (- (length l)
         (length sl))
      #f))

For many situations, one may want indexes of all occurrences of item in the list. One can get a list of all indexes as follows:

(define (indexes_of1 x l)
  (let loop ((l l)
             (ol '())
             (idx 0))
    (cond
      [(empty? l) (reverse ol)]
      [(equal? (first l) x)
       (loop (rest l)
             (cons idx ol)
             (add1 idx))]
      [else
       (loop (rest l)
             ol
             (add1 idx))])))

For/list can also be used for this:

(define (indexes_of2 x l)
  (for/list ((i l)
             (n (in-naturals))
             #:when (equal? i x))
    n))

Testing:

(indexes_of1 'a '(a b c a d e a f g))
(indexes_of2 'a '(a b c a d e a f g))

Output:

'(0 3 6)
'(0 3 6)

Comments

[Alex V]

How bizarre. Would the racket-dev mailing list be the appropriate outlet for recommending this feature to be added to the language?

[Óscar López]

I guess ... but it's not a big deal given that it's so simple to implement.

[Óscar López]

@Maxwell I had forgotten about list-index. See my updated answer.

[Alex V]

Thanks Oscar, I am going to use that, you are amazing.

[C. K. Young]

You're the first non-Racket-dev I know who uses curry, congrats. :-) (I usually tend to use cut for similar situations, where true currying isn't required, because you can insert arguments in the middle, like this.)

[Eli Barzilay]

Note that acc is a pretty bad name here, since it doesn't really accumulate anything.

[Óscar López]

@EliBarzilay agreed, fixed it!

[Eli Barzilay]

@ÓscarLópez: Well, I'd have some other stylistic comments on your code, like the use of round parens, and the related newline in the let bindings, but I usually keep them to myself...

[Óscar López]

@EliBarzilay I know, but old habits die hard

[raffomania]

Why would you use list-index instead of car (filter ...)?

[Óscar López]

@raffomania because filter returns a list of elements, we're interested in a single element. And besides, there's no way to specify an index to be returned when using filter. Simply put, it's not the right tool for the job

[Fabien]

@ChrisJester-Young Maybe this is a better link for cut.

[C. K. Young]

@Fabien The intent was to present a real use case for cut, which involved linking to real code that used it. It wasn't to provide documentation for people who didn't already know what cut was.

[Fabien]

@ÓscarLópez I would suggest you to swap the two halves of your answer, for quick readers like me who stop reading before the end. I think the most important information is that there is a procedure.

[Mulan]

@Fabien I disagree. I think the most important information (wrt this answer) for a programmer to know is that he/she should feel empowered by their language to implement any procedure they feel is missing. If you later come to learn that a built-in procedure exists, you can use it in new programs and/or refactor old programs. Stopping to task the internet every time you need a basic procedure is only short-cutting yourself.

[Alex Knauth]

Please please don't do the -1 thing to signal that there is no index. It's much clearer and easier if you return #false in those cases, so that's the idiomatic way to do it

[djfdev]

As of Racket 6.7 index-of is now part of the standard library! This might be worthy of an edit (although this answer works perfectly fine).

[djfdev]

@ÓscarLópez thank you! I'm learning racket and your SO posts have been indispensable so far