Position of All Matching Elements in List

Question

I'm trying to write a function in Common Lisp similar to the built in position function, that returns a list of the positions of all elements in the haystack that match the needle, as opposed to just the first. I've come up with a few possible solutions (for example recursively searching for the next element using a cdr-from function on the position and adding the result to the previous position) but none of the approaches I've come up with so far seem particularly elegant.

Can anyone suggest what would be the best way of approaching this, as I'm currently struggling.

Answer 1

The obvious way to solve the problem is just to look at each element of the list in turn, and each time one compares as equal to the needle collect its position into an output list. Getting the position is very easy in this case, because we are starting from the beginning of haystack; we can use a variable to count the current position starting from 0.

So if we describe the full algorithm in a sentence, we'd say something like "to find all the positions of a needle in a haystack, for each element in the haystack, and the position starting from 0, when the element is equal to the needle, collect the position."

The LOOP facility is basically the right thing to break out when you want to do iterative processing. Even though its syntax is complicated to describe formally, after some experience you can pretty much just put the English-language description of the algorithm in the body of LOOP and it will work.

(defun all-positions (needle haystack)
  (loop
    for element in haystack 
    and position from 0
     when (eql element needle)
      collect position))

Answer 2

Take this one with a grain of salt (and be sure to load Alexandria beforehand):

(defun positions (item sequence &key (test #'eql))
  (mapcar #'car
          (remove item (map 'list #'cons (alexandria:iota (length sequence)) sequence)
                       :test-not test
                       :key #'cdr)))

That said, it does have the advantage of working on arbitrary sequences:

CL-USER> (positions 'x #(x x y y x x y y))
(0 1 4 5)
CL-USER> (positions 5 (list 5.0 -1 5 5.0 -1) :test #'=)
(0 2 3)
CL-USER> (positions #\l "Hello")
(2 3)

Answer 3

If you want a recursive function, rather than a (loop ...) based one, you could use something like:

(defun all-positions (needle haystack)
    (labels ((f (n h c r)
                 (if (null h)
                     r
                     (if (eql (car h) n)
                         (f n (cdr h) (1+ c) (cons c r))
                         (f n (cdr h) (1+ c) r))))))
    (reverse (f needle haystack 0 nil)))

Answer 4

Here's another (not necessarily better) way to do it.

(defun get-positions (needle haystack)
  (let ((result nil))
    (dotimes (i (length haystack))
      (if (eq (nth i haystack) needle)
          (push i result)))
    (nreverse result)))