Лисп индекса Найти в списке

Question

Поэтому у меня есть список целых чисел, и я пытаюсь найти индекс, где

list(i) > list(i+1) 

У меня есть базовые случаи, когда, если список пуст или длина 1, она возвращает длина списка, но у меня возникают проблемы с фактическим перемещением списка и отслеживанием индекса.

код я прямо сейчас:

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

) 

Answer 1

Написать рекурсивную функцию, которая принимает аргумент для «количества узлов уже пройденных». В пределах out-of-order вызовите эту функцию с номером 0 как уже пройденным номером.

... Достаточно ли вам намека? Попробуйте еще раз и посмотрите, сможете ли вы его получить.

ЕЩЕ ПОДСКАЗКА

(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... 
     ))) 

Answer 2

Вот своего рода шаблон, в котором изложен подход к проблеме.

(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))) 

Подумайте о частях процесса (#<these things>) сами по себе, а также как каждый из них вносит вклад в решение. Заполнение их приведет вас к решению, и я думаю, что также поможет вам лучше понять рекурсивные процедуры.

Конечно, прокомментируйте, если есть какие-либо детали, которые неясны.

Если вы не знакомы с labels, вот той же самой логикой, но с использованием вместо внешней процедуры помощника:

(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)) 

Answer 3

Там нет необходимости делать это рекурсивно. В Common Lisp более идиоматично выражать это как явный цикл. Это приводит к более переносимому коду, поскольку нет необходимости в реализации Common Lisp для устранения хвостовых вызовов.

Вы можете решить это с помощью простого loop. У вас есть три переменные цикла: текущий элемент, следующий элемент и текущий индекс. Как только вы найдете текущий и следующий элемент, которые удовлетворяют условию, вы возвращаете текущий индекс.

(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))))) 

(Специальное поведение, чтобы вернуть длину списка, если такой индекс не найден вызывает довольно специальной начальный караул и добавление 2 в конце. Было бы больше обычного, чтобы вернуться nil в этом случае, но, возможно, есть некоторая оптимизация в окружающем использовании.)