CLisp - сортировка и объединение двух списков в быстрой сортировке - PullRequest
Новая
       59

CLisp - сортировка и объединение двух списков в быстрой сортировке

1 голос
/ 08 мая 2019

Я пытаюсь реализовать быструю сортировку в CLisp, и до сих пор я могу разделить список вокруг оси. Однако, когда я пытаюсь объединить и рекурсивно отсортировать подсписки, я получаю либо переполнение стека, либо ошибку с let, и я не уверен, что происходит не так. Вот мой код: 

(defun pivot (n xs)
  (list (getLesser n xs) (getGreater n xs))
)

(defun getLesser (m l)
  (cond
    ((null l) nil)
    ((<= m (car l)) (getLesser m (cdr l)))
    (t (cons (car l) (getLesser m (cdr l)))))
)

(defun getGreater (m l)
  (cond
    ((null l) nil)
    ((> m (car l)) (getGreater m (cdr l)))
    (t (cons (car l) (getGreater m (cdr l)))))
)


(defun quicksort (xs)
  (cond
    ((null xs) nil)
    (t
      (let (partition (pivot (car xs) xs))
        (cond
          ((null (car partition)) (cons (quicksort (cdr partition)) nil))
          ((null (cdr partition)) (cons (quicksort (car partition)) nil))
          (t (append (quicksort (car partition)) (quicksort (cdr partition)))))))))

Моя идея заключалась в том, чтобы иметь локальную переменную partition, которая представляет собой список из 2 списков, где car partition - это список чисел, меньших, чем сводная, а cdr partition - список чисел, больших, чем сводная. Затем, в финальной конструкции cond, если бы не было чисел, меньших, чем пивот, я бы рекурсивно отсортировал 2-й список; если бы не было чисел, превышающих точку разворота, я бы отсортировал первый список; иначе я бы рекурсивно отсортировал оба и добавил их по порядку. Кто-нибудь может мне помочь?

Ответы [ 2 ]

2 голосов
/ 08 мая 2019

Компиляция файла дает вам подсказки о неправильном синтаксисе.

GNU CLISP производит следующие диагностики: 

$ clisp -q -c foo.lisp
;; Compiling file /tmp/foo.lisp ...
WARNING: in QUICKSORT in lines 20..28 : Illegal syntax in LET/LET*: (PIVOT (CAR XS) XS)
         Ignore the error and proceed
;; Deleted file /tmp/foo.fas
There were errors in the following functions:
 QUICKSORT
1 error, 1 warning

SBCL производит подобные диагностики: 

$ sbcl --eval '(compile-file "foo.lisp")' --quit
This is SBCL 1.3.1.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
; compiling file "/tmp/foo.lisp" (written 08 MAY 2019 08:58:54 PM):
; compiling (DEFUN PIVOT ...)
; compiling (DEFUN GETLESSER ...)
; compiling (DEFUN GETGREATER ...)
; compiling (DEFUN QUICKSORT ...)
; file: /tmp/foo.lisp
; in: DEFUN QUICKSORT
;     (LET (PARTITION (PIVOT (CAR XS) XS))
;       (COND ((NULL (CAR PARTITION)) (CONS (QUICKSORT #) NIL))
;             ((NULL (CDR PARTITION)) (CONS (QUICKSORT #) NIL))
;             (T (APPEND (QUICKSORT #) (QUICKSORT #)))))
; 
; caught ERROR:
;   The LET binding spec (PIVOT (CAR XS) XS) is malformed.
; 
; compilation unit finished
;   caught 1 ERROR condition


; /tmp/foo.fasl written
; compilation finished in 0:00:00.021

Вы можетезатем найдите ожидаемый синтаксис в CLHS : http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/speope_letcm_letst.html

1 голос
/ 09 мая 2019

Синтаксис для LET: (LET BINDINGS. BODY) , где BINDINGS - список привязок;каждая привязка представляет собой список (ЗНАЧЕНИЕ СИМВОЛА) .Кроме того, привязка может быть просто SYMBOL , что означает (SYMBOL NIL) .Ваш код: 

(let (partition (pivot (car xs) xs))
  ...)

Давайте напишем одну привязку на строку и нормализуем все привязки как правильный список: 

(let ((partition nil)
      (pivot (car xs) xs)))
  ...)

Вы можете видеть, что код:

  • связывает partition с NIL
  • имеет некорректное второе связывание: есть три элемента, а именно pivot, (car xs) и xs, которые не соответствуют ожидаемым (СИМВОЛVALUE) синтаксис.
...