The position of all relevant items in the list.

Question

I am trying to write a function in Common Lisp, similar to the built-in position function, which returns a list of the positions of all the elements in the haystack corresponding to the needle, and not just the first. I came up with several possible solutions (for example, recursively searching for the next element using the cdr-from function in the position and adding the result to the previous position), but none of the approaches that I have not found so far seem particularly elegant.

Can anyone suggest what would be the best way to approach this since I am fighting now.

Answer 1

The obvious way to solve the problem is to simply look at each element of the list in turn, and each time it is compared with an equal needle, it takes its position to the output list. Getting a position is very simple in this case, because we start from the beginning of the haystack; we can use a variable to calculate the current position, starting from 0.

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

The LOOP function is basically the right thing to break out when you want to do iterative processing. Despite the fact that its syntax is more difficult to formally describe after some experience, you can pretty much just put the English-language description of the algorithm in the LOOP body, 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 with salt (and be sure to download Alexandria in advance):

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

However, he has the advantage of working on arbitrary sequences:

 CL-USER> (positions 'x #(xxyyxxyy)) (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 need a recursive function, not one based on (loop ...) , you can use something like:

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

Answer 4

Here's another (not necessarily the best) way to do this.

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