lisp 中的快速排序显示 lambda 函数错误
Quicksort in lisp shows lambda function error
我为快速排序编写了以下代码，与 C 代码非常相似。但是这里它只读取 list.after 的元素，它说分区函数应该是 lambda function.I' m lisp 的新手。请帮助 me.My 代码是：-
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i)
)
(defun quicksort(start end)
(if (< start end)
((setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end))))
)
(defun partition(start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
((setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j)
)
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp)
)
(quicksort 0 10)
想知道这个 lambda 是什么function.whether它只是一个尚未定义的函数的匿名名称
如果你想在 if 的正文中使用多个语句，你不能只用 ( ) 包裹它们。在 Lisp 中，双括号是有意义的；他们不适合分组。
你的选择是
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
或
(when (< (aref A j) pivot)
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex))
我会一步一步来。首先，使用标准格式：
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i))
(defun quicksort (start end)
(if (< start end)
((setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end)))))
(defun partition (start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
((setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
解决当前的问题：括号总是包围表格，他们不
自行分组。
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i))
(defun quicksort (start end)
(if (< start end)
(progn
(setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end)))))
(defun partition (start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
一些错误，逐行：
(print "Enter the elements of the array")
(setq k 10) ; warning: no variable K
(setq A (make-array '(10))) ; warning: no variable A
(setq i 0) ; warning: no variable I
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i)) ; warning: k never used
(defun quicksort (start end)
(if (< start end)
(progn
(setq pindex (lambda (start end))) ; this lambda always returns nil
(quicksort (start (- pindex 1))) ; START is not a function
(quicksort ((+ pindex 1) end))))) ; (+ PINDEX 1) is not a function
(defun partition (start end)
(setq pivot (aref A end)) ; warning: no variable PIVOT
(setq pindex start) ; warning: no variable PINDEX
(setq j 0) ; warning: no variable J
(loop
(if (>= j end) return) ; warning: no variable RETURN
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex)) ; warning: no variable TEMP
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
去掉 "no variable" 警告。 Setq不引入变量。
大多数 Common Lisp 实现都做了一些有用的事情，因此这似乎可行，
但这是未定义的行为。您可以全局声明这些变量
defvar 或 defparameter 的特殊之处，但您在这里实际需要的是
读取用户输入的功能，您可以在其中使用 let 进行本地化
绑定。它还 returns 读取数组而不是设置全局状态。我
也选择使用 K 作为参数以实现一些使用的灵活性。 Finish-output
确保在输入第一个数字之前显示提示。
(defun read-integers (k)
(print "Enter the elements of the array.")
(finish-output)
(let ((a (make-array (list k)))
(i 0))
(loop
(if (>= i k)
(return))
(let ((x (read)))
(setf (aref a i) x)
(incf i)))
a))
这仍然有很大的改进空间，但至少它是有效的。
下一步：修复quicksort。因为它不使用 partition 除了运动以外的任何地方
一个空的 lambda 表格，我假设您想在那里调用 partition。我
还修复了调用表单和丢失的绑定：
(defun quicksort (start end)
(if (< start end)
(let ((pindex (partition start end)))
(quicksort start (- pindex 1))
(quicksort (+ pindex 1) end))))
这对一个你在它的任何地方都没有提到的全局数组进行操作
body。这非常令人困惑，并且使代码非常难以阅读并且
无法维护。最好把数组作为参数，这样你
称其为 (quicksort (read-integers 10) 0 10).
为了性能，我们需要就地操作，这很不寻常，以至于
它应该在文档字符串中提到。我 return 数组，以便通常
排序语义可以用于它。没有替代条款的 IF 是
最好写成 WHEN。
(defun quicksort (array start end)
"Destructively sorts ARRAY in place."
(when (< start end)
(let ((pindex (partition array start end)))
(quicksort array start (- pindex 1))
(quicksort array (+ pindex 1) end)))
array)
这仍然包含 off-by-one 错误，但我现在将查看 partition。
首先，解决常见的绑定问题：
(defun partition (array start end)
"Chooses an arbitrary pivot element from array between START and END, then
destructively partitions the elements of ARRAY between START and END
in-place into those smaller than the pivot, then the pivot, then those
bigger than the pivot. Finally returns the index of the pivot."
;; FIXME: doesn't work
(let ((pivot (aref array end))
(pindex start)
(j 0))
(loop
(if (>= j end) (return))
(if (< (aref array j) pivot)
(let ((temp (aref array pindex)))
(setf pindex (aref array j))
(setf (aref array j) temp)
(incf pindex)))
(incf j))
(let ((temp (aref array pindex)))
(setf (aref array pindex) pivot)
(setf (aref array end) temp))))
这是完全错误的。请查看快速排序的工作原理。
提示：
- 你需要两个索引变量
- 您不应引用 START 和 END 之外的数组部分
- 提示：不要通过明确的临时位置手动交换，而是使用
rotatef
- 提示：
position-if 可能会有用。在 Hyperspec 中查找。
- 提示：自行测试
partition。当它工作时，修复 quicksort.
我为快速排序编写了以下代码，与 C 代码非常相似。但是这里它只读取 list.after 的元素，它说分区函数应该是 lambda function.I' m lisp 的新手。请帮助 me.My 代码是：-
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i)
)
(defun quicksort(start end)
(if (< start end)
((setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end))))
)
(defun partition(start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
((setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j)
)
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp)
)
(quicksort 0 10)
想知道这个 lambda 是什么function.whether它只是一个尚未定义的函数的匿名名称
如果你想在 if 的正文中使用多个语句，你不能只用 ( ) 包裹它们。在 Lisp 中，双括号是有意义的；他们不适合分组。
你的选择是
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
或
(when (< (aref A j) pivot)
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex))
我会一步一步来。首先，使用标准格式：
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i))
(defun quicksort (start end)
(if (< start end)
((setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end)))))
(defun partition (start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
((setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
解决当前的问题：括号总是包围表格，他们不 自行分组。
(print "Enter the elements of the array")
(setq k 10)
(setq A (make-array '(10)))
(setq i 0)
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i))
(defun quicksort (start end)
(if (< start end)
(progn
(setq pindex (lambda (start end)))
(quicksort(start (- pindex 1)))
(quicksort((+ pindex 1) end)))))
(defun partition (start end)
(setq pivot (aref A end))
(setq pindex start)
(setq j 0)
(loop
(if (>= j end) return)
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex))
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
一些错误，逐行：
(print "Enter the elements of the array")
(setq k 10) ; warning: no variable K
(setq A (make-array '(10))) ; warning: no variable A
(setq i 0) ; warning: no variable I
(loop
(if (>= i 10) (return))
(setq x (read))
(setf (aref A i) x)
(incf i)) ; warning: k never used
(defun quicksort (start end)
(if (< start end)
(progn
(setq pindex (lambda (start end))) ; this lambda always returns nil
(quicksort (start (- pindex 1))) ; START is not a function
(quicksort ((+ pindex 1) end))))) ; (+ PINDEX 1) is not a function
(defun partition (start end)
(setq pivot (aref A end)) ; warning: no variable PIVOT
(setq pindex start) ; warning: no variable PINDEX
(setq j 0) ; warning: no variable J
(loop
(if (>= j end) return) ; warning: no variable RETURN
(if (< (aref A j) pivot)
(progn
(setq temp (aref A pindex)) ; warning: no variable TEMP
(setq pindex (aref A j))
(setq (aref A j) temp)
(incf pindex)))
(incf j))
(setq temp (aref A pindex))
(setq (aref A pindex) pivot)
(setq (aref A end) temp))
(quicksort 0 10)
去掉 "no variable" 警告。 Setq不引入变量。
大多数 Common Lisp 实现都做了一些有用的事情，因此这似乎可行，
但这是未定义的行为。您可以全局声明这些变量
defvar 或 defparameter 的特殊之处，但您在这里实际需要的是
读取用户输入的功能，您可以在其中使用 let 进行本地化
绑定。它还 returns 读取数组而不是设置全局状态。我
也选择使用 K 作为参数以实现一些使用的灵活性。 Finish-output
确保在输入第一个数字之前显示提示。
(defun read-integers (k)
(print "Enter the elements of the array.")
(finish-output)
(let ((a (make-array (list k)))
(i 0))
(loop
(if (>= i k)
(return))
(let ((x (read)))
(setf (aref a i) x)
(incf i)))
a))
这仍然有很大的改进空间，但至少它是有效的。
下一步：修复quicksort。因为它不使用 partition 除了运动以外的任何地方
一个空的 lambda 表格，我假设您想在那里调用 partition。我
还修复了调用表单和丢失的绑定：
(defun quicksort (start end)
(if (< start end)
(let ((pindex (partition start end)))
(quicksort start (- pindex 1))
(quicksort (+ pindex 1) end))))
这对一个你在它的任何地方都没有提到的全局数组进行操作
body。这非常令人困惑，并且使代码非常难以阅读并且
无法维护。最好把数组作为参数，这样你
称其为 (quicksort (read-integers 10) 0 10).
为了性能，我们需要就地操作，这很不寻常，以至于 它应该在文档字符串中提到。我 return 数组，以便通常 排序语义可以用于它。没有替代条款的 IF 是 最好写成 WHEN。
(defun quicksort (array start end)
"Destructively sorts ARRAY in place."
(when (< start end)
(let ((pindex (partition array start end)))
(quicksort array start (- pindex 1))
(quicksort array (+ pindex 1) end)))
array)
这仍然包含 off-by-one 错误，但我现在将查看 partition。
首先，解决常见的绑定问题：
(defun partition (array start end)
"Chooses an arbitrary pivot element from array between START and END, then
destructively partitions the elements of ARRAY between START and END
in-place into those smaller than the pivot, then the pivot, then those
bigger than the pivot. Finally returns the index of the pivot."
;; FIXME: doesn't work
(let ((pivot (aref array end))
(pindex start)
(j 0))
(loop
(if (>= j end) (return))
(if (< (aref array j) pivot)
(let ((temp (aref array pindex)))
(setf pindex (aref array j))
(setf (aref array j) temp)
(incf pindex)))
(incf j))
(let ((temp (aref array pindex)))
(setf (aref array pindex) pivot)
(setf (aref array end) temp))))
这是完全错误的。请查看快速排序的工作原理。
提示：
- 你需要两个索引变量
- 您不应引用 START 和 END 之外的数组部分
- 提示：不要通过明确的临时位置手动交换，而是使用
rotatef - 提示：
position-if可能会有用。在 Hyperspec 中查找。 - 提示：自行测试
partition。当它工作时，修复quicksort.