CODEWITHSUNDEEP
lisp
Cristiano
Cristiano

Reputation: 2909

Lisp Find index in a list

So I have a list of integers and I'm trying to find the index where 

list(i) > list(i+1)

I have the base cases where if the list is empty or length 1, it returns the list length, but I'm having trouble with actually traversing the list and keeping track of the index.

The code I have right now:

(defunc out-of-order (l)
(cond ((or (equal (length l) 0) (equal (length l) 1)) (length l))
    ; this is where the index search goes

)

Upvotes: 2

Views: 3973

Answers (3)

Svante
Svante

Reputation: 51501

There is no need to do this recursively. In Common Lisp, it is more idiomatic to express this as an explicit loop. That results in more portable code, since there is no requirement for a Common Lisp implementation to eliminate tail calls.

You can solve this with a simple loop. You have three loop variables: the current element, the next element, and the current index. As soon as you find a current and next element that satisfy the condition, you return the current index.

(defun find-downstep-index (list)
  (if (endp (rest list))
      (length list)
      (loop :for current-element :in list
            :for next-element :in (rest list)
            :for current-index :upfrom 0
            :when (> current-element next-element)
            :do (return-from find-downstep-index current-index)
            :finally (return (+ current-index 2)))))

(The special behaviour to return the length of the list if no such index is found causes the rather ad hoc initial guard and the addition of 2 at the end. It would be more usual to return nil in this case, but perhaps there is some optimization in the surrounding use going on.)

Upvotes: 1

jbm
jbm

Reputation: 2600

Here's a sort of template outlining an approach to the problem.

(defun out-of-order (list)
  (labels ((recur (list index)
             (cond ((or #<list is empty> #<list only has one item>)
                    nil)
                   ((> #<the first item> #<the second item>)
                    index)
                   (t
                    (recur #<advance the recursion> #<increment the index>)))))
    (recur list 0)))

Think about the parts of the process (#<these things>) by themselves and also how they each contribute to the solution. Filling them in will lead you to the solution and I think also help you better understand recursive procedures.

Of course, please comment if there are any parts that are unclear.

If you're not familiar with labels, here's the same logic but using an external helper procedure instead:

(defun out-of-order-aux (list index)
  (cond ((or #<list is empty> #<list only has one item>)
         nil)
        ((> #<the first item> #<the second item>)
         index)
        (t
         (out-of-order-aux #<advance the recursion> #<increment the index>))))

(defun out-of-order (list)
  (out-of-order-aux list 0))

Upvotes: 2

Alex D
Alex D

Reputation: 30445

Write a recursive function which takes an argument for "number of nodes already traversed". Within out-of-order, call that function with 0 as the number already traversed.

...Is that enough of a hint for you? Try again and see if you can get it.

ANOTHER HINT

 (defun out-of-order (lst)
   (out-of-order-rec lst 0))
 (defun out-of-order-rec (lst i)
   (if (or (endp lst) (endp (cdr lst)))
      ; something...
      (if (> (car lst) (car (cdr lst)))
         ; something...
         ; something...
         )))

Upvotes: 2

Related Questions