Проблема сортировки вставки Lisp - PullRequest
Новая
       5

Проблема сортировки вставки Lisp

2 голосов
/ 19 июля 2011

Используйте insert, чтобы написать функцию sort1, которая сортирует список целых чисел в порядке возрастания. [Мы закончили, если список равен нулю. В противном случае вставьте автомобиль из списка в отсортированный CDR.]

Это то, что мне удалось сделать, и у меня возникли проблемы с определением обеих функций в одной функции sort1: 

(defun insert (item lst &optional (key #'<))
  (if (null lst)
    (list item)
  (if (funcall key item (car lst))
          (cons item lst) 
          (cons (car lst) (insert item (cdr lst) key)))))
(defun insertion-sort (lst &optional (key #'<))
  (if (null lst)
    lst
    (insert (car lst) (insertion-sort (cdr lst) key) key)))

1 Ответ

3 голосов
/ 19 июля 2011

Самый простой способ получить все это в одном определении функции - это использовать labels для определения функции insert как локальной функции внутри insertion-sort.

Однако о вашем коде можно сказать еще несколько вещей:

  • Вам не нужно переименовывать переменную как lst из-за боязни столкновения с функцией list: в Common Lisp функции и переменные живут в разных пространствах имен.
  • Обычной практикой является упрощение шаблона (if (null list) list (...)) до (and list (...)), поскольку, если (null list) истинно, тогда list должно быть nil!
  • Ваш аргумент key имеет неправильное имя: функция key - это функция, которая берет элемент списка и возвращает ключ для сравнения ( см. HyperSpec для sort). То, что у вас есть (функция, которая сравнивает два элемента), называется «предикатом».
  • Если у вас есть паттерн (if ... (if ...)), то обычно понятнее, если вы используете cond.
  • Нет документации!

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

(defun insertion-sort (list &optional (predicate #'<))
  "Return a sorted copy of list. Optional argument predicate must be a function
that takes two items and returns true if they are in order."
  (labels ((insert (item list)
                   (cond ((null list) (list item))
                         ((funcall predicate item (car list))
                          (cons item list))
                         (t (cons (car list) (insert item (cdr list)))))))
    (and list (insert (car list) (insertion-sort (cdr list) predicate)))))

Обратите внимание, что теперь, когда insert является локальным для insertion-sort, мне не нужно передавать ему аргумент predicate, поскольку внутренняя функция выбирает привязку из окружающего контекста.

...