Ваша insert функция очень странная. На самом деле, мне так трудно читать, что я не могу понять, что он делает, за исключением того, что нет необходимости проверять, является ли список нулевым и его CDR равным нулю. Он также включает в себя множество вещей, в которых он не нуждается, если только вы не обязаны какой-то частью спецификации задачи делать копии вставляемых вами пакетов.
Вот его версия, которая намного легче читать и который не копирует, когда это не нужно. Обратите внимание, что он принимает аргументы в другом порядке:
(defun insert (thing into)
(cond ((null into)
(list thing))
((< (car thing) (car (first into)))
(cons thing into))
(t (cons (first into)
(insert thing (rest into))))))
Теперь, каков алгоритм сортировки вставкой? Ну, по сути это:
- l oop над списком для сортировки:
- для каждого элемента, вставьте его в отсортированный список;
- наконец вернуть отсортированный список.
И нам не разрешено использовать присвоение для этого.
Ну, для этого есть стандартный прием вещь, которая заключается в использовании хвостовой рекурсивной функции с аргументом аккумулятор , который накапливает результаты. Мы можем либо написать эту функцию как явную вспомогательную функцию, либо сделать ее локальной функцией. Я собираюсь сделать последнее и потому, что нет никакой причины для функции, которая когда-либо использовалась только локально, чтобы быть видимой глобально, и потому что (поскольку я предполагаю, что это домашняя работа), это затрудняет прямую отправку.
Итак, вот эта версия функции:
(defun insertion-sort (l)
(labels ((is-loop (tail sorted)
(if (null tail)
sorted
(is-loop (rest tail) (insert (first tail) sorted)))))
(is-loop l '())))
Этот подход довольно естествен в Scheme, но не очень естествен в CL. Альтернативный подход, который не использует присваивание, по крайней мере явно, заключается в использовании do. Вот версия, которая использует do:
(defun insertion-sort (l)
(do ((tail l (rest tail))
(sorted '() (insert (first tail) sorted)))
((null tail) sorted)))
Есть две заметки об этой версии.
- Прежде всего, хотя это не явно используя назначение, оно довольно явно неявно делает это. Я думаю, что это, вероятно, обман.
- Во-вторых, это немного неуловимо, почему это работает: каково значение
tail в (insert (first tail) sorted) и почему?
A версия, которая более понятна, но использует loop, о которой вы, вероятно, не должны знать, это
(defun insertion-sort (l)
(loop for e in l
for sorted = (insert e '()) then (insert e sorted)
finally (return sorted)))
Это, однако, также довольно явно использует присваивание.
Как и у Каз как указано ниже, есть очевидный способ (который я должен был увидеть!) сделать это с помощью функции CL reduce. Концептуально reduce состоит в том, чтобы последовательно свернуть последовательность элементов, вызвав функцию, которая принимает два аргумента. Так, например,
(reduce #'+ '(1 2 3 4))
совпадает с
(+ (+ (+ 1 2) 3) 4)
Это легче увидеть, если использовать cons в качестве функции:
> > (reduce #'cons '(1 2 3 4))
(((1 . 2) . 3) . 4)
> (cons (cons (cons 1 2) 3) 4)
(((1 . 2) . 3) . 4)
Ну, конечно, insert, как определено выше, действительно подходит для этого: он берет упорядоченный список и вставляет в него новую пару, возвращая новый упорядоченный список. Есть две проблемы:
- my
insert принимает свои аргументы в неправильном порядке (возможно, именно поэтому исходный принял аргументы в другом порядке!); - там должен быть способом «заполнения» исходного отсортированного списка, который будет
().
Что ж, мы можем исправить неправильный порядок аргументов, переписав insert, или просто оборачивая его в функцию, которая меняет аргументы: я сделаю последнее, потому что я не хочу пересматривать то, что я написал выше, и я не хочу две версии функции.
Вы можете 'начать' 'начальное нулевое значение, либо просто добавляя его к списку вещей для сортировки, либо на самом деле reduce имеет специальную опцию для предоставления начального значения, поэтому мы будем использовать это.
Итак, используя reduce мы получаем эту версию insertion-sort:
(defun insertion-sort (l)
(reduce (lambda (a e)
(insert e a))
l :initial-value '()))
И мы можем проверить это:
> (insertion-sort '((1 . a) (-100 . 2) (64.2 . "x") (-2 . y)))
((-100 . 2) (-2 . y) (1 . a) (64.2 . "x"))
и она отлично работает.
Итак, последний вопрос is: мы снова обманывали, используя некоторую функцию, определение которой, очевидно, должно вызывать У меня есть задание? Ну, нет, это не так, потому что вы можете довольно легко написать упрощенный reduce и увидеть, что для него не нужно использовать присваивание. Эта версия намного проще, чем CL reduce, и, в частности, для нее явно требуется аргумент начального значения:
(defun reduce/simple (f list accum)
(if (null list)
accum
(reduce/simple f (rest list) (funcall f accum (first list)))))
(Опять же, это не очень естественный код CL, поскольку он основан на исключении хвостовых вызовов обрабатывать большие списки, но это дает понять, что вы можете сделать это без присваивания.)
И теперь мы можем написать одну окончательную версию insertion-sort:
(defun insertion-sort (l)
(reduce/simple (lambda (a e)
(insert e a))
l '()))
легко проверить, что это также работает.