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

20,591

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)
Share:
20,591
Alex V
Author by

Alex V

I like learning backwards. Seeing what something is and imagining how it could have been made. And then finding ways to make it do things it shouldn't.

Updated on August 12, 2020

Comments

  • Alex V
    Alex V over 2 years

    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?

  • Alex V
    Alex V over 9 years
    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
    Óscar López over 9 years
    I guess ... but it's not a big deal given that it's so simple to implement.
  • Óscar López
    Óscar López over 9 years
    @Maxwell I had forgotten about list-index. See my updated answer.
  • Alex V
    Alex V over 9 years
    Thanks Oscar, I am going to use that, you are amazing.
  • C. K. Young
    C. K. Young over 9 years
    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
    Eli Barzilay over 9 years
    Note that acc is a pretty bad name here, since it doesn't really accumulate anything.
  • Óscar López
    Óscar López over 9 years
    @EliBarzilay agreed, fixed it!
  • Eli Barzilay
    Eli Barzilay over 9 years
    @Ó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
    Óscar López over 9 years
    @EliBarzilay I know, but old habits die hard
  • raffomania
    raffomania about 9 years
    Why would you use list-index instead of car (filter ...)?
  • Óscar López
    Óscar López about 9 years
    @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
    Fabien almost 9 years
    @ChrisJester-Young Maybe this is a better link for cut.
  • C. K. Young
    C. K. Young almost 9 years
    @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
    Fabien almost 9 years
    @Ó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
    Mulan about 6 years
    @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
    Alex Knauth about 6 years
    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
    djfdev about 5 years
    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
    djfdev about 5 years
    @ÓscarLópez thank you! I'm learning racket and your SO posts have been indispensable so far