Фильтр на основе предыдущий данных

В F# я бы такое делал через fold, тут есть описание и примеры использования:

http://msdn.microsoft.com/ru-ru/library/ee353894.aspx

Вкратце:

fold проходится по последовательности(слева на право) и к каждому элементу применяет функцию f: S*X -> S, где X - тип элементов последовательности, S - состояние. Результат работы - конечное состояние. Кроме f fold принимает в качестве аргументов начальное состояние (из S) и последовательность.

п.с. в lisp аналог будет называться reduce вроде.

Хм. Ведь reduce может накапливать результат не только в атом (как я им обычно пользоватлся), но и в список! Сейчас буду пробовать, спасибо.

(nreverse (cadr (reduce (lambda (state x)
                         (let ((prev (etypecase state
                                       (number state)
                                       (cons (car state)))))
                          (when (atom state)
                           (setf state (list state (list state))))
                          (when (< (- x prev) 2)
                           (push x (cadr state)))
                          (setf (car state) x)
                          state)) '(1 2 4 7 8 9))))

state хранит в себе список: первый элемент - предыдущее значение проходимого списка, второй элемент - накапливаемый результирующий список. Просто хранить в state результирующий список нельзя, иначе для (1 2 4 7 8 9) потеряются подходящие под условие 8 и 9.

Получилось полное дерьмо, требуются свежие идеи!

(loop for prev = nil then x
   for x in '(1 2 4 7 8 9)
   do (format t "~a - ~a~%" x prev)
   when (or (null prev)
            (< (- x prev) 2))
   collect x)

Аналогичное решение с помощью loop.

А если добавить немного мутабельности?

(defun foo (list n)
  (let ((prev))
    (nreverse
     (reduce (lambda (acc num)
	       (prog1
		   (if (or (not prev)
			   (<= (- num prev) n))
		       (cons num acc)
		       acc)
		 (setf prev num))) 
	     list :initial-value '()))))

CL-USER> (foo '(1 3 8 15 16 18) 2)
(1 3 16 18)
CL-USER> 

Лучше, но все равно очень много кода на такую простую прикладную задачу. Просто окинув код взглядом, не понятно, что он делает.

Никто не говорил, что вариант с reduce будет самым оптимальным по читаемости ☺ По сути, тело лямбды аналогично телу цикла, просто в последнем сахарку больше, отчего он выглядит естественнее.

Если только на одном предыдущем — то свертка, как здесь уже сказали. Если на нескольких предыдущих или на N-ном предыдущем — то уже не обойтись без дополнительного списка.

Нафига все эти when и setf тебе? Там одного if хватит, на F# (лиспа нету под рукой, но идея должна быть понятна):

let my_filter n lst =
    List.tail lst |>
    Seq.fold (fun (prev, res) elem ->
        if (elem - prev) < n then
            (elem, elem::res)
        else (elem, res)) (List.head lst, [List.head lst])
    |> second |> List.rev

Заюз:

> let mf3 = my_filter 3;;

val mf3 : (int list -> int list)

> mf3 [1; 2; 3; 10; 12; 13];;
val it : int list = [1; 2; 3; 12; 13]

Не идеально, но для примера сойдёт.

П.С. считаю, что первый элемент списка мы допускаем в любом случае.

theNamelessOne прав, если loop тебе позволяет написать это проще и читабельнее - пиши через loop (идея одна и та же, реализация - мелочи, главное чтобы не тормозило). Главное всё это завернуть в функцию, чтобы удобно юзать было.

И не страшно такие конструкции рожать?

(defun foo (list n)
  (iter (for x in list)
        (for prev previous x)
        (when (<= (- x (or prev (car list))) n)
          (collect x))))

Тоже самое, только с использование loop:

(defun foo (list n)
  (loop for x in list
        and prev = x
        when (<= (- x (or prev (car list))) n)
          collect x))

Здесь используется parallel bindings. Подробности здесь.

Вообще чуть намудрил проверку, лучше так:

Для iterate:

(defun foo (list n)
  (iter (for x in list)
        (for prev previous x)
        (when (or (null prev)
                  (<= (- x prev) n))
          (collect x))))

Для loop:

(defun foo (list n)
  (loop for x in list
        and prev = x
        when (or (null prev)
                 (<= (- x prev) n))
            collect x))

Красота!