为什么这个排序算法会做它应该做的事情？ [口齿不清]

Question

我正在复习旧考试，为自己的考试做准备，教授非常好，还为我们提供了解决方案，现在我想知道为什么一个函数会做它应该做的事情。

(defun sortulists (L)
  (mapcar (lambda (uliste)
            (sort uliste (lambda (x1 x2)
                           (or (symbolp x2)
                               (and (numberp x1) (numberp x2)
                                    (< x1 x2))))))
          L))

它应该采用一个列表 L，其中包含未排序的子列表，其中可能包含数字和原子，首先对它的数字进行排序，然后将符号放在最后。

当这样调用时 (sortulists '((A 9 b h 2) (1 m n 9 8) (5 a 7))) 它 returns ((2 9 H B A) (1 8 9 N M) (5 7 A)).

有什么帮助吗？

编辑：固定缩进

Answer 1

sort 函数的谓词说明一旦序列被排序，什么测试必须为真。未定义如何进行排序。

如果您对此处使用的 and 和 or 感到困惑，我建议您阅读 Common Lisp: A Gentle Introduction to Symbolic Computation 的条件章节。它展示了如何互换 cond、嵌套 if 以及组合 and 和 or，并提供练习（及其解决方案）。

简而言之，要么右边必须有符号，要么，如果都是数字，则必须按大小排序。

Answer 2

(or
    ; if x2 is a symbol, then x1 is smaller, whatever x1 is
    (symbolp x2)

    ; if both are numbers, then return t if x1 is smaller than x2
    (and (numberp x1) (numberp x2)
         (< x1 x2)))

所以数字是排序的并且在前面。符号在末尾，但未排序。

Answer 3

因此，显而易见的是：

(defun sortulists (L)
  (mapcar (lambda (uliste)
            (sort uliste (lambda (x1 x2)
                           (or (symbolp x2)
                               (and (numberp x1) (numberp x2)
                                    (< x1 x2))))))
          L))

mapcar 只是列出了将匿名函数应用于每个元素的列表。所以只关注一个元素 '(A 9 b h 2) 你可以这样做：

;; same as the anonymous lambda, but named so we can test it a little
(defun my< (x1 x2)
  (or (symbolp x2)
      (and (numberp x1) (numberp x2)
           (< x1 x2))))

(sort '(A  9  b  h  2) #'my<) ; ==> (2 9 B H A)

(my< 2 'a)                    ; ==> T 
(my< 2 3)                     ; ==> T
(my< 3 3)                     ; ==> NIL
(my< 'a 2)                    ; ==> NIL
(my< 'a 'b)                   ; ==> T
(my< 'b 'a)                   ; ==> T

看my< 如果x2是一个符号，x1比x2小。如果 x1 都是数字并且 x1 在算术上小于 x2，则它们也更小。对于其他一切，x1 等于或大于 x2。

如果您稍微混合参数列表中的符号，您可能会发现您得到的符号顺序与原始列表不同。原因是比较的两个符号都会变成 t，所以 'a 小于 'b 而 'b 小于 'a。我们在结果中保持符号顺序的版本如下所示：

(stable-sort '(A  9  b  h  2)
      (lambda (x1 x2)
        (and (numberp x1) 
             (or (not (numberp x2))
                 (< x1 x2)))))
; ==> (2 9 A B H)

注意我使用了 stable-sort 函数，因为 sort 不能保证稳定。稳定意味着相同的对象保持与源相同的顺序。

为什么这个排序算法会做它应该做的事情？ [口齿不清]

Why does this sorting algorithm do what it is supposed to? [Lisp]

lisp

sorting

common-lisp