不确定为什么 let 函数没有正确返回 sbcl lisp 中的值
Not sure why let function isn't properly returning the value in sbcl lisp
所以我写了一个函数来按'value'（对的第二部分）对无序对列表进行排序。这是我对递归函数的尝试（我知道它有一个基本的设计）：
*编辑功能设计：该功能由：
获取无序对列表、排序频率列表和递归调用的可选 startList。它首先将 listRet 设置为等于 startList。
如果无序列表只有一个元素，则该元素被推到listRet。
如果列表大于 1，则循环遍历每对无序列表并检查它是否等于有序频率列表的第一个元素。
如果不是最后一个元素，则推入listRet。
然后循环继续，直到遇到最后一个元素，然后递归调用该函数，并从无序列表中删除推送对，因为它已正确放入 listRet 和最高频率. listRet 作为可选的 startList 参数放置到位。
现在如果无序列表有多个元素并且最后一个元素是排序的正确频率，我选择将该元素移动到列表的前面并进行递归打电话。
现在可以提取无序列表的第一个元素，然后我滥用 do 循环到达列表的末尾，并再次进行递归函数调用，如步骤 5 所示。
First If 语句在无序列表长度为 1 后退出（如步骤 2 中所示）并且 listRet 应该 returned。
函数：
(defun sort-by-freq (listUnord listOrdFreqs &optional startList)
(print startList)
(let ((listRet startList)) ;; step 1
(if (equal (length listUnord) 1) ;;step 2
;;(print listRet)
(push (car listUnord) listRet)
(loop for pair in listUnord ;;step 3
do (if (and (equal (cdr pair) (car listOrdFreqs))
(not (equal (last-element-by-pair listUnord)(car pair))))
(push pair listRet) ;;step 4
(if (and (equal (cdr pair) (car listOrdFreqs))
(equal (last-element-by-pair listUnord)(car pair)))
(sort-by-freq (append (list (cons (car pair) (cdr pair)))
(remove-element listUnord pair))
listOrdFreqs listRet) ;;step 6
(if (equal (last-element-by-pair listUnord)(car pair))
(sort-by-freq (remove-element listUnord (car listRet))
(cdr listOrdFreqs)
listRet)))))) ;; step 5
listRet)) ;;step 8
所以如果我调用：
(sort-by-freq (list(cons 'c 2)(cons 'b 3)(cons 'a 1)) '(3 2 1))
我期待结果：
((A . 1) (C . 2) (B . 3))
但出于某种原因，在 return 我只得到：
((B . 3))
使用 (print startList) 语句，我可以确认 startList 正在按我希望的方式构建。它输出：
NIL
((B . 3))
((B . 3))
((C . 2) (B . 3))
并且我已经通过注释掉的;;(print retList)确认了在输出((C . 2) (B . 3))之后达到了退出条件。 (push (car listUnord) listRet) 应该将第三个元素 (A . 1) 推到列表的前面并 returning listRet。这与我设计其他带有输出的函数的方式一致，并且有效。
我错过了什么？
*这里编辑我使用的两个辅助函数：
(defun remove-element (origPairList origPair)
(let ((retlist (list)))
(loop for pair in origPairList
do (if (not(equal(car origPair)(car pair)))
(push pair retlist)))
retlist))
(defun last-element-by-pair (pairList)
(let ((lastEl (car (car pairList))))
(if (not (null (cdr pairList)))
(loop for el in pairList
do (setf lastEl (car el))))
lastEl))
一些提示...
简化事情:
(defun remove-element (origPairList origPair)
(let ((retlist (list)))
(loop for pair in origPairList
do (if (not(equal(car origPair)(car pair)))
(push pair retlist)))
retlist))
至
(defun remove-element (list pair)
(remove (car pair) list :key #'car))
和
(defun last-element-by-pair (pairList)
(let ((lastEl (car (car pairList))))
(if (not (null (cdr pairList)))
(loop for el in pairList
do (setf lastEl (car el))))
lastEl))
到
(defun last-element-by-pair (pair-list)
(caar (last pair-list)))
一团糟car/cdr。在 LOOP 中使用解构。
(loop for pair in foo ... (car pair) ... (cdr pair) ... (car pair) ...)
是
(loop for (head . tail) in foo ... head ... tail ... head ...)
不要一直走清单
然后
(if (equal (length foo) 1) ...)
是
(if (and (consp foo) (rest foo)) ...) ; no need to traverse the list
进一步的问题：
您还需要确保您的代码缩进正确。通常在编辑器中击键来做到这一点。此外，您的代码缺少右括号。因此，该代码在语法上是不正确的。
(defun sort-by-freq (listUnord listOrdFreqs &optional startList)
(print startList)
(let ((listRet startList))
(if (equal (length listUnord) 1)
(push (car listUnord) listRet) ;; <- this makes no sense.
;; since you quit the function
;; there is no useful effect
(loop for pair in listUnord
do (if (and (equal (cdr pair) (car listOrdFreqs))
(not (equal (last-element-by-pair listUnord)(car pair) )))
(push pair listRet)
(if (and (equal (cdr pair) (car listOrdFreqs))
(equal (last-element-by-pair listUnord)(car pair)))
;; this call to sort-by-freq makes no sense.
;; you are not using the return value
(sort-by-freq ;; what are you appending here, only one list?
(append (list (cons (car pair) (cdr pair))
(remove-element listUnord pair)))
listOrdFreqs
listRet)
(if (equal (last-element-by-pair listUnord)(car pair))
;; this call to sort-by-freq makes no sense.
;; you are not using the return value
(sort-by-freq (remove-element listUnord (car listRet))
(cdr listOrdFreqs)
listRet))))))
listRet))
基本上在
(loop for e in list
do (compute-some-thing-and-return-it e))
调用该函数没有任何意义，因为未使用 return 值。调用该函数的唯一原因是它是否有副作用。
示例：
CL-USER 310 > (loop for e in '(1 2 3 4)
do (if (evenp e)
(* e 10)
(* e 100)))
NIL
如您所见，它 return 为 NIL。可能不是你想要的。
主要问题
您正在 do 子句中的循环内计算表达式。这
returned 值永远不会在任何地方使用。
函数的return值由局部变量listRet给出，
它在函数的开头设置并恰好在
2个地方，两次调用push。第一个只发生一个
输入大小为 1 的列表。第二次推送仅在第 4 步发生。
我们可以很容易地看到所有其他操作都没有任何效果
在本地 listRet 变量上。另外，因为 sort-by-freq 也是
因为你的辅助功能是纯粹的（它们永远不会破坏
listRet 指向的列表结构），你也知道列表是
不会通过以不同方式链接其 cons 单元来修改
随着时间的推移。
让我们通过使用您的示例跟踪您的代码来确认这一点：
(trace sort-by-freq last-element-by-pair remove-element)
评估测试时，会发出以下跟踪（输出因实现而异，此处使用的是 SBCL）：
0: (SORT-BY-FREQ ((C . 2) (B . 3) (A . 1)) (3 2 1))
1: (LAST-ELEMENT-BY-PAIR ((C . 2) (B . 3) (A . 1)))
1: LAST-ELEMENT-BY-PAIR returned A
1: (LAST-ELEMENT-BY-PAIR ((C . 2) (B . 3) (A . 1)))
1: LAST-ELEMENT-BY-PAIR returned A
1: (LAST-ELEMENT-BY-PAIR ((C . 2) (B . 3) (A . 1)))
1: LAST-ELEMENT-BY-PAIR returned A
1: (REMOVE-ELEMENT ((C . 2) (B . 3) (A . 1)) (B . 3))
1: REMOVE-ELEMENT returned ((A . 1) (C . 2))
1: (SORT-BY-FREQ ((A . 1) (C . 2)) (2 1) ((B . 3)))
2: (LAST-ELEMENT-BY-PAIR ((A . 1) (C . 2)))
2: LAST-ELEMENT-BY-PAIR returned C
2: (LAST-ELEMENT-BY-PAIR ((A . 1) (C . 2)))
2: LAST-ELEMENT-BY-PAIR returned C
2: (LAST-ELEMENT-BY-PAIR ((A . 1) (C . 2)))
2: LAST-ELEMENT-BY-PAIR returned C
2: (REMOVE-ELEMENT ((A . 1) (C . 2)) (C . 2))
2: REMOVE-ELEMENT returned ((A . 1))
2: (SORT-BY-FREQ ((C . 2) (A . 1)) (2 1) ((B . 3)))
3: (LAST-ELEMENT-BY-PAIR ((C . 2) (A . 1)))
3: LAST-ELEMENT-BY-PAIR returned A
3: (LAST-ELEMENT-BY-PAIR ((C . 2) (A . 1)))
3: LAST-ELEMENT-BY-PAIR returned A
3: (REMOVE-ELEMENT ((C . 2) (A . 1)) (C . 2))
3: REMOVE-ELEMENT returned ((A . 1))
3: (SORT-BY-FREQ ((A . 1)) (1) ((C . 2) (B . 3)))
3: SORT-BY-FREQ returned ((A . 1) (C . 2) (B . 3))
2: SORT-BY-FREQ returned ((C . 2) (B . 3))
1: SORT-BY-FREQ returned ((B . 3))
0: SORT-BY-FREQ returned ((B . 3))
可以看到的一个小问题是
last-element-by-pair 使用相同的输入多次调用，这
很浪费。循环之前可以调用一次。
在第 0 级，函数迭代对直到找到 (B . 3)，
其频率等于第二个列表中的第一个频率。这是
第 4 步，将 pair 推到由
sort-by-freq.
调用中的局部变量 listRet
当循环到达无序列表的最后一个元素时，
函数被递归调用（i）一个新的无序对列表，
使用 remove-element 计算，(ii) 少一个频率，(iii) 当前
绑定到 listRet.
的列表
但是无论在递归步骤中发生什么，特别是无论递归调用产生什么结果，当前的绑定
in scope for listRet 将不再修改。此外，
当前由 listRet 指向的列表的结构未被修改
（例如，使用 nconc 或 rplacd）。
在 2 级及以下级别完成的所有工作都是关于推动价值
本地命名为 listRet 的临时变量前面，然后丢弃它们。
What am I missing?
从 sort-by-freq 的递归调用到
该函数的当前调用已损坏，您必须表达
根据递归结果的当前结果，或者你需要改变
事情（但不鼓励这样做）。
命名和用户界面
Taking a list of unordered pairs, a list of sorted frequencies, and
an optional startList for recursive calls. It first sets listRet
equal to the startList.
根据您的说明，我将函数定义如下：
(defun sort-pairs-by-frequencies (pairs frequencies)
...)
递归是否需要额外的参数
调用不是函数用户关心的问题。那样
细节应该被隐藏，除非你真的想要你的用户
能够将列表作为第三个参数传递。
复杂的极端情况
If the unordered list has only one element, that element is pushed
to listRet. [...] If it is not the last element, it is pushed to the
listRet.
递归列表的函数通常只需要考虑两个
案例：空列表和非空列表。事实上，你考虑得更多
极端情况，比如一个元素的列表，或者当你检查一个元素时
元素是最后一个，是一面巨大的红旗。有问题
需要有复杂的基础条件，但是这个可以在一个
更简单的方法。
冗余测试
除了对 last-element-by-pair 的多次调用外，还请注意
您在功能的不同点重复测试，即使
在给定的上下文中它们必然是正确的。
(if (and (equal (cdr pair) (car listOrdFreqs))
(not (equal (last-element-by-pair listUnord)(car pair))))
(push pair listRet) ;;step 4
(if (and (equal (cdr pair) (car listOrdFreqs))
(equal (last-element-by-pair listUnord)(car pair)))
(sort-by-freq (append (list (cons (car pair) (cdr pair)))
(remove-element listUnord pair))
listOrdFreqs listRet) ;;step 6
(if (equal (last-element-by-pair listUnord)(car pair))
(sort-by-freq (remove-element listUnord (car listRet))
(cdr listOrdFreqs)
listRet))))
给定适当的定义，上面可以写成：
(if (and A (not B))
(step-4)
(if (and A B)
(step-6)
(if B (step-5))))
让我们写下每一步的条件是什么，基于什么
它们属于 if 表达式树的分支：
对于第 4 步：(and a (not b)) 必然成立，因为它在 if.
对于第 5 步：(and b (not a))，基于路径谓词的以下简化：
(and b
(not (and a b))
(not (and a (not b))))
=> (and b
(or (not a) (not b))
(or (not a) b))
=> (and b (or (not a) nil) t)
=> (and b (not a))
第 6 步：(and a b)
因此，您可以将测试编写为：
(cond
(a (if b (step-6) (step-4)))
(b (step-5)))
更简单的版本
If the list is larger than 1 each pair of the unordred list is
looped through and checked if it equals the first element of the
ordered frequency list.
以上是算法的核心。对于每个频率 F，你
将无序元素分成两个列表：一个是
频率等于F，其他的。
让我们来定义一下：如何根据是否删除或保留项目
它们的频率与给定频率匹配。以下不是
必然有效，但它有效且简单。此外，它出错了
仅使用不可变操作要谨慎：
(defun remove-frequency (pairs frequency)
(remove frequency pairs :test #'= :key #'cdr))
(defun keep-frequency (pairs frequency)
(remove frequency pairs :test-not #'= :key #'cdr))
(remove-frequency '((a . 20) (b . 10) (c . 5) (d . 20)) 20)
=> ((B . 10) (C . 5))
(keep-frequency '((a . 20) (b . 10) (c . 5) (d . 20)) 20)
=> ((A . 20) (D . 20))
然后，你的主函数递归频率：
(defun sort-pairs-by-frequencies (pairs frequencies)
(if (null frequencies)
pairs
(destructuring-bind (frequency . frequencies) frequencies
(append (keep-frequency pairs frequency)
(sort-pairs-by-frequencies (remove-frequency pairs frequency)
frequencies)))))
当没有给出排序依据的频率时，未排序的对列表是
return编辑。否则，frequencies 可以被解构为一个 cons cell，
其中第一项是 frequency，其余项是
frequencies。请注意，frequencies 的先前绑定是
阴影，因为从这一点开始我们不需要参考
整个频率列表了。
然后，一般情况下函数的 return 值计算为
附加具有给定频率和列表的对
不匹配的对 frequency，递归排序
剩余的频率。
(sort-pairs-by-frequencies '((a . 20) (b . 10) (c . 5) (d . 20))
'(5 10 20))
=> ((C . 5) (B . 10) (A . 20) (D . 20))
通过先评估 (trace sort-pairs-by-frequencies)，您还
获得以下跟踪：
0: (SORT-PAIRS-BY-FREQUENCIES ((A . 20) (B . 10) (C . 5) (D . 20)) (5 10 20))
1: (SORT-PAIRS-BY-FREQUENCIES ((A . 20) (B . 10) (D . 20)) (10 20))
2: (SORT-PAIRS-BY-FREQUENCIES ((A . 20) (D . 20)) (20))
3: (SORT-PAIRS-BY-FREQUENCIES NIL NIL)
3: SORT-PAIRS-BY-FREQUENCIES returned NIL
2: SORT-PAIRS-BY-FREQUENCIES returned ((A . 20) (D . 20))
1: SORT-PAIRS-BY-FREQUENCIES returned ((B . 10) (A . 20) (D . 20))
0: SORT-PAIRS-BY-FREQUENCIES returned ((C . 5) (B . 10) (A . 20) (D . 20))
以上函数的编写是为了便于阅读
"trivially" 正确，但它们仍然在浪费内存和堆栈。其他方法可以使用循环（常量堆栈使用）对元素进行就地排序（无内存分配）。
我用一个不太复杂的解决方案解决了这个问题。虽然我承认这里的其他张贴者写了更优雅的解决方案，但它们与我的尝试无关。我想使用此时我理解的基本语法来解决这个问题。
这是我的新 sort-by-frequency 函数的样子：
(defun sort-by-frequency (pairs frequencies)
(let ((retList (list)))
(loop for freq in frequencies
do (push (extract-pair-match pairs freq (extract-keys retList)) retList))
retList))
我现在使用一个简单的循环遍历频率列表，然后使用函数 extract-pair-match 根据频率找到一个匹配项，该函数还从变量 retList 以便它可以搜索并确保相同的键不会出现两次。
函数如下：
(defun extract-pair-match(pairs match keys)
(if (and (equal (cdr(car pairs)) match) (not (search-keys keys (car(car pairs)))))
(car pairs)
(extract-pair-match (cdr pairs) match keys)))
首先它检查列表 pairs 的第一项以查看它的键是否匹配 match，然后它在 keys 列表上使用函数 search-keys（它在 sort-by-frequency 中的 retList 处传递，以确保该键还不是列表的一部分。如果是，它将继续到下一个术语。所做的假设是每个频率都有一个匹配。
这里是 search-keys 函数：
(defun search-keys (keys match)
(if (null keys)
nil
(if (equal (car keys) match)
(car keys)
(search-keys (cdr keys) match))))
这里是 extract-keys 函数：
(defun extract-keys (pairList)
(let ((retlist (list (car (car pairList)))))
(loop for pair in (cdr pairList)
do (push (car pair) retlist))
retlist))
所以现在如果我这样做：
(sort-by-frequency (list(cons 'c 2)(cons 'b 3)(cons 'a 1)) '(1 2 3))
我得到：
((A . 1) (C . 2) (B . 3))
所以我写了一个函数来按'value'（对的第二部分）对无序对列表进行排序。这是我对递归函数的尝试（我知道它有一个基本的设计）：
*编辑功能设计：该功能由：
获取无序对列表、排序频率列表和递归调用的可选 startList。它首先将 listRet 设置为等于 startList。
如果无序列表只有一个元素，则该元素被推到
listRet。如果列表大于 1，则循环遍历每对无序列表并检查它是否等于有序频率列表的第一个元素。
如果不是最后一个元素，则推入listRet。
然后循环继续，直到遇到最后一个元素，然后递归调用该函数，并从无序列表中删除推送对，因为它已正确放入 listRet 和最高频率. listRet 作为可选的 startList 参数放置到位。
现在如果无序列表有多个元素并且最后一个元素是排序的正确频率，我选择将该元素移动到列表的前面并进行递归打电话。
现在可以提取无序列表的第一个元素，然后我滥用 do 循环到达列表的末尾，并再次进行递归函数调用，如步骤 5 所示。
First If 语句在无序列表长度为 1 后退出（如步骤 2 中所示）并且
listRet应该 returned。
函数：
(defun sort-by-freq (listUnord listOrdFreqs &optional startList)
(print startList)
(let ((listRet startList)) ;; step 1
(if (equal (length listUnord) 1) ;;step 2
;;(print listRet)
(push (car listUnord) listRet)
(loop for pair in listUnord ;;step 3
do (if (and (equal (cdr pair) (car listOrdFreqs))
(not (equal (last-element-by-pair listUnord)(car pair))))
(push pair listRet) ;;step 4
(if (and (equal (cdr pair) (car listOrdFreqs))
(equal (last-element-by-pair listUnord)(car pair)))
(sort-by-freq (append (list (cons (car pair) (cdr pair)))
(remove-element listUnord pair))
listOrdFreqs listRet) ;;step 6
(if (equal (last-element-by-pair listUnord)(car pair))
(sort-by-freq (remove-element listUnord (car listRet))
(cdr listOrdFreqs)
listRet)))))) ;; step 5
listRet)) ;;step 8
所以如果我调用：
(sort-by-freq (list(cons 'c 2)(cons 'b 3)(cons 'a 1)) '(3 2 1))
我期待结果：
((A . 1) (C . 2) (B . 3))
但出于某种原因，在 return 我只得到：
((B . 3))
使用 (print startList) 语句，我可以确认 startList 正在按我希望的方式构建。它输出：
NIL
((B . 3))
((B . 3))
((C . 2) (B . 3))
并且我已经通过注释掉的;;(print retList)确认了在输出((C . 2) (B . 3))之后达到了退出条件。 (push (car listUnord) listRet) 应该将第三个元素 (A . 1) 推到列表的前面并 returning listRet。这与我设计其他带有输出的函数的方式一致，并且有效。
我错过了什么？
*这里编辑我使用的两个辅助函数：
(defun remove-element (origPairList origPair)
(let ((retlist (list)))
(loop for pair in origPairList
do (if (not(equal(car origPair)(car pair)))
(push pair retlist)))
retlist))
(defun last-element-by-pair (pairList)
(let ((lastEl (car (car pairList))))
(if (not (null (cdr pairList)))
(loop for el in pairList
do (setf lastEl (car el))))
lastEl))
一些提示...
简化事情:
(defun remove-element (origPairList origPair)
(let ((retlist (list)))
(loop for pair in origPairList
do (if (not(equal(car origPair)(car pair)))
(push pair retlist)))
retlist))
至
(defun remove-element (list pair)
(remove (car pair) list :key #'car))
和
(defun last-element-by-pair (pairList)
(let ((lastEl (car (car pairList))))
(if (not (null (cdr pairList)))
(loop for el in pairList
do (setf lastEl (car el))))
lastEl))
到
(defun last-element-by-pair (pair-list)
(caar (last pair-list)))
一团糟car/cdr。在 LOOP 中使用解构。
(loop for pair in foo ... (car pair) ... (cdr pair) ... (car pair) ...)
是
(loop for (head . tail) in foo ... head ... tail ... head ...)
不要一直走清单
然后
(if (equal (length foo) 1) ...)
是
(if (and (consp foo) (rest foo)) ...) ; no need to traverse the list
进一步的问题：
您还需要确保您的代码缩进正确。通常在编辑器中击键来做到这一点。此外，您的代码缺少右括号。因此，该代码在语法上是不正确的。
(defun sort-by-freq (listUnord listOrdFreqs &optional startList)
(print startList)
(let ((listRet startList))
(if (equal (length listUnord) 1)
(push (car listUnord) listRet) ;; <- this makes no sense.
;; since you quit the function
;; there is no useful effect
(loop for pair in listUnord
do (if (and (equal (cdr pair) (car listOrdFreqs))
(not (equal (last-element-by-pair listUnord)(car pair) )))
(push pair listRet)
(if (and (equal (cdr pair) (car listOrdFreqs))
(equal (last-element-by-pair listUnord)(car pair)))
;; this call to sort-by-freq makes no sense.
;; you are not using the return value
(sort-by-freq ;; what are you appending here, only one list?
(append (list (cons (car pair) (cdr pair))
(remove-element listUnord pair)))
listOrdFreqs
listRet)
(if (equal (last-element-by-pair listUnord)(car pair))
;; this call to sort-by-freq makes no sense.
;; you are not using the return value
(sort-by-freq (remove-element listUnord (car listRet))
(cdr listOrdFreqs)
listRet))))))
listRet))
基本上在
(loop for e in list
do (compute-some-thing-and-return-it e))
调用该函数没有任何意义，因为未使用 return 值。调用该函数的唯一原因是它是否有副作用。
示例：
CL-USER 310 > (loop for e in '(1 2 3 4)
do (if (evenp e)
(* e 10)
(* e 100)))
NIL
如您所见，它 return 为 NIL。可能不是你想要的。
主要问题
您正在 do 子句中的循环内计算表达式。这
returned 值永远不会在任何地方使用。
函数的return值由局部变量listRet给出，
它在函数的开头设置并恰好在
2个地方，两次调用push。第一个只发生一个
输入大小为 1 的列表。第二次推送仅在第 4 步发生。
我们可以很容易地看到所有其他操作都没有任何效果
在本地 listRet 变量上。另外，因为 sort-by-freq 也是
因为你的辅助功能是纯粹的（它们永远不会破坏
listRet 指向的列表结构），你也知道列表是
不会通过以不同方式链接其 cons 单元来修改
随着时间的推移。
让我们通过使用您的示例跟踪您的代码来确认这一点：
(trace sort-by-freq last-element-by-pair remove-element)
评估测试时，会发出以下跟踪（输出因实现而异，此处使用的是 SBCL）：
0: (SORT-BY-FREQ ((C . 2) (B . 3) (A . 1)) (3 2 1))
1: (LAST-ELEMENT-BY-PAIR ((C . 2) (B . 3) (A . 1)))
1: LAST-ELEMENT-BY-PAIR returned A
1: (LAST-ELEMENT-BY-PAIR ((C . 2) (B . 3) (A . 1)))
1: LAST-ELEMENT-BY-PAIR returned A
1: (LAST-ELEMENT-BY-PAIR ((C . 2) (B . 3) (A . 1)))
1: LAST-ELEMENT-BY-PAIR returned A
1: (REMOVE-ELEMENT ((C . 2) (B . 3) (A . 1)) (B . 3))
1: REMOVE-ELEMENT returned ((A . 1) (C . 2))
1: (SORT-BY-FREQ ((A . 1) (C . 2)) (2 1) ((B . 3)))
2: (LAST-ELEMENT-BY-PAIR ((A . 1) (C . 2)))
2: LAST-ELEMENT-BY-PAIR returned C
2: (LAST-ELEMENT-BY-PAIR ((A . 1) (C . 2)))
2: LAST-ELEMENT-BY-PAIR returned C
2: (LAST-ELEMENT-BY-PAIR ((A . 1) (C . 2)))
2: LAST-ELEMENT-BY-PAIR returned C
2: (REMOVE-ELEMENT ((A . 1) (C . 2)) (C . 2))
2: REMOVE-ELEMENT returned ((A . 1))
2: (SORT-BY-FREQ ((C . 2) (A . 1)) (2 1) ((B . 3)))
3: (LAST-ELEMENT-BY-PAIR ((C . 2) (A . 1)))
3: LAST-ELEMENT-BY-PAIR returned A
3: (LAST-ELEMENT-BY-PAIR ((C . 2) (A . 1)))
3: LAST-ELEMENT-BY-PAIR returned A
3: (REMOVE-ELEMENT ((C . 2) (A . 1)) (C . 2))
3: REMOVE-ELEMENT returned ((A . 1))
3: (SORT-BY-FREQ ((A . 1)) (1) ((C . 2) (B . 3)))
3: SORT-BY-FREQ returned ((A . 1) (C . 2) (B . 3))
2: SORT-BY-FREQ returned ((C . 2) (B . 3))
1: SORT-BY-FREQ returned ((B . 3))
0: SORT-BY-FREQ returned ((B . 3))
可以看到的一个小问题是
last-element-by-pair 使用相同的输入多次调用，这
很浪费。循环之前可以调用一次。
在第 0 级，函数迭代对直到找到 (B . 3)，
其频率等于第二个列表中的第一个频率。这是
第 4 步，将 pair 推到由
sort-by-freq.
listRet
当循环到达无序列表的最后一个元素时，
函数被递归调用（i）一个新的无序对列表，
使用 remove-element 计算，(ii) 少一个频率，(iii) 当前
绑定到 listRet.
但是无论在递归步骤中发生什么，特别是无论递归调用产生什么结果，当前的绑定
in scope for listRet 将不再修改。此外，
当前由 listRet 指向的列表的结构未被修改
（例如，使用 nconc 或 rplacd）。
在 2 级及以下级别完成的所有工作都是关于推动价值
本地命名为 listRet 的临时变量前面，然后丢弃它们。
What am I missing?
从 sort-by-freq 的递归调用到
该函数的当前调用已损坏，您必须表达
根据递归结果的当前结果，或者你需要改变
事情（但不鼓励这样做）。
命名和用户界面
Taking a list of unordered pairs, a list of sorted frequencies, and an optional startList for recursive calls. It first sets listRet equal to the startList.
根据您的说明，我将函数定义如下：
(defun sort-pairs-by-frequencies (pairs frequencies)
...)
递归是否需要额外的参数 调用不是函数用户关心的问题。那样 细节应该被隐藏，除非你真的想要你的用户 能够将列表作为第三个参数传递。
复杂的极端情况
If the unordered list has only one element, that element is pushed to listRet. [...] If it is not the last element, it is pushed to the listRet.
递归列表的函数通常只需要考虑两个 案例：空列表和非空列表。事实上，你考虑得更多 极端情况，比如一个元素的列表，或者当你检查一个元素时 元素是最后一个，是一面巨大的红旗。有问题 需要有复杂的基础条件，但是这个可以在一个 更简单的方法。
冗余测试
除了对 last-element-by-pair 的多次调用外，还请注意
您在功能的不同点重复测试，即使
在给定的上下文中它们必然是正确的。
(if (and (equal (cdr pair) (car listOrdFreqs))
(not (equal (last-element-by-pair listUnord)(car pair))))
(push pair listRet) ;;step 4
(if (and (equal (cdr pair) (car listOrdFreqs))
(equal (last-element-by-pair listUnord)(car pair)))
(sort-by-freq (append (list (cons (car pair) (cdr pair)))
(remove-element listUnord pair))
listOrdFreqs listRet) ;;step 6
(if (equal (last-element-by-pair listUnord)(car pair))
(sort-by-freq (remove-element listUnord (car listRet))
(cdr listOrdFreqs)
listRet))))
给定适当的定义，上面可以写成：
(if (and A (not B))
(step-4)
(if (and A B)
(step-6)
(if B (step-5))))
让我们写下每一步的条件是什么，基于什么 它们属于 if 表达式树的分支：
对于第 4 步：
(and a (not b))必然成立，因为它在 if. 的 "then" 分支中
对于第 5 步：
(and b (not a))，基于路径谓词的以下简化：(and b (not (and a b)) (not (and a (not b)))) => (and b (or (not a) (not b)) (or (not a) b)) => (and b (or (not a) nil) t) => (and b (not a))第 6 步：
(and a b)
因此，您可以将测试编写为：
(cond
(a (if b (step-6) (step-4)))
(b (step-5)))
更简单的版本
If the list is larger than 1 each pair of the unordred list is looped through and checked if it equals the first element of the ordered frequency list.
以上是算法的核心。对于每个频率 F，你 将无序元素分成两个列表：一个是 频率等于F，其他的。
让我们来定义一下：如何根据是否删除或保留项目 它们的频率与给定频率匹配。以下不是 必然有效，但它有效且简单。此外，它出错了 仅使用不可变操作要谨慎：
(defun remove-frequency (pairs frequency)
(remove frequency pairs :test #'= :key #'cdr))
(defun keep-frequency (pairs frequency)
(remove frequency pairs :test-not #'= :key #'cdr))
(remove-frequency '((a . 20) (b . 10) (c . 5) (d . 20)) 20)
=> ((B . 10) (C . 5))
(keep-frequency '((a . 20) (b . 10) (c . 5) (d . 20)) 20)
=> ((A . 20) (D . 20))
然后，你的主函数递归频率：
(defun sort-pairs-by-frequencies (pairs frequencies)
(if (null frequencies)
pairs
(destructuring-bind (frequency . frequencies) frequencies
(append (keep-frequency pairs frequency)
(sort-pairs-by-frequencies (remove-frequency pairs frequency)
frequencies)))))
当没有给出排序依据的频率时，未排序的对列表是
return编辑。否则，frequencies 可以被解构为一个 cons cell，
其中第一项是 frequency，其余项是
frequencies。请注意，frequencies 的先前绑定是
阴影，因为从这一点开始我们不需要参考
整个频率列表了。
然后，一般情况下函数的 return 值计算为
附加具有给定频率和列表的对
不匹配的对 frequency，递归排序
剩余的频率。
(sort-pairs-by-frequencies '((a . 20) (b . 10) (c . 5) (d . 20))
'(5 10 20))
=> ((C . 5) (B . 10) (A . 20) (D . 20))
通过先评估 (trace sort-pairs-by-frequencies)，您还
获得以下跟踪：
0: (SORT-PAIRS-BY-FREQUENCIES ((A . 20) (B . 10) (C . 5) (D . 20)) (5 10 20))
1: (SORT-PAIRS-BY-FREQUENCIES ((A . 20) (B . 10) (D . 20)) (10 20))
2: (SORT-PAIRS-BY-FREQUENCIES ((A . 20) (D . 20)) (20))
3: (SORT-PAIRS-BY-FREQUENCIES NIL NIL)
3: SORT-PAIRS-BY-FREQUENCIES returned NIL
2: SORT-PAIRS-BY-FREQUENCIES returned ((A . 20) (D . 20))
1: SORT-PAIRS-BY-FREQUENCIES returned ((B . 10) (A . 20) (D . 20))
0: SORT-PAIRS-BY-FREQUENCIES returned ((C . 5) (B . 10) (A . 20) (D . 20))
以上函数的编写是为了便于阅读 "trivially" 正确，但它们仍然在浪费内存和堆栈。其他方法可以使用循环（常量堆栈使用）对元素进行就地排序（无内存分配）。
我用一个不太复杂的解决方案解决了这个问题。虽然我承认这里的其他张贴者写了更优雅的解决方案，但它们与我的尝试无关。我想使用此时我理解的基本语法来解决这个问题。
这是我的新 sort-by-frequency 函数的样子：
(defun sort-by-frequency (pairs frequencies)
(let ((retList (list)))
(loop for freq in frequencies
do (push (extract-pair-match pairs freq (extract-keys retList)) retList))
retList))
我现在使用一个简单的循环遍历频率列表，然后使用函数 extract-pair-match 根据频率找到一个匹配项，该函数还从变量 retList 以便它可以搜索并确保相同的键不会出现两次。
函数如下：
(defun extract-pair-match(pairs match keys)
(if (and (equal (cdr(car pairs)) match) (not (search-keys keys (car(car pairs)))))
(car pairs)
(extract-pair-match (cdr pairs) match keys)))
首先它检查列表 pairs 的第一项以查看它的键是否匹配 match，然后它在 keys 列表上使用函数 search-keys（它在 sort-by-frequency 中的 retList 处传递，以确保该键还不是列表的一部分。如果是，它将继续到下一个术语。所做的假设是每个频率都有一个匹配。
这里是 search-keys 函数：
(defun search-keys (keys match)
(if (null keys)
nil
(if (equal (car keys) match)
(car keys)
(search-keys (cdr keys) match))))
这里是 extract-keys 函数：
(defun extract-keys (pairList)
(let ((retlist (list (car (car pairList)))))
(loop for pair in (cdr pairList)
do (push (car pair) retlist))
retlist))
所以现在如果我这样做：
(sort-by-frequency (list(cons 'c 2)(cons 'b 3)(cons 'a 1)) '(1 2 3))
我得到：
((A . 1) (C . 2) (B . 3))