CLisp

Question

我正在尝试在 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 构造中，如果没有数字小于主元，我将递归地对第二个列表进行排序；如果没有大于主元的数字，我将对第一个列表进行排序；否则我会递归地对两者进行排序并按顺序附加它们。谁能帮帮我？

Answer 1

编译文件时会提示语法错误。

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

中查找预期的语法

Answer 2

LET 的语法是 (LET BINDINGS . BODY)，其中 BINDINGS 是绑定列表；每个绑定都是一个 (SYMBOL VALUE) 列表。或者，绑定可以只是 SYMBOL，代表 (SYMBOL NIL)。您的代码是：

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

让我们每行编写一个绑定并将所有绑定规范化为适当的列表：

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

可以看到代码：

将 partition 绑定到 NIL
第二个绑定格式错误：有三个元素，即pivot、(car xs)和xs，与预期的(SYMBOL VALUE)不匹配 语法。

CLisp - 在快速排序中排序和合并两个列表

CLisp - sorting and combining two lists in quicksort

syntax

recursion

common-lisp

let