Lisp - 使用自定义函数排序

Question

我在 Lisp 中有这个函数：

(defun AddtoQueue (queue method)
  (cond
    ( (eq method 'DFS) (append (growPath (car queue)  (findCh (caar queue))) (cdr queue) ) )
    ( (eq method 'BFS) (append (cdr queue) (growPath (car queue)(findCh (caar queue))) ) )
    ( (eq method 'A) (SORT  (append (cdr queue) (growPath (car queue) (findCh (caar queue)) ) ) #'> :key #'pathLength  ) )
    (T "not implemented")
  )
)  

我必须使用自定义函数（此处名为pathLength）对列表进行排序。我阅读了 lisp 的文档，sort但我什么都不懂。我的问题是我到底在为我的比较函数提供什么？

比较功能：

(defun pathLength(point)

    ;;distance from origin point
    (setq x (- (length queue) 1) ) 

    ;;distance from end(manhattan distance) by subtracting the coords.
    ;;calc lists is adding or subtracting lists.
    (setq y (calcLists (cadr (assoc (car point) coords)) (cadr (assoc terminal coords)) 'sub ) )


    (setq y (+ (car y) (cadr y) ) )
    ;;sum of distance from start and end.
    (+ x y)
)

Answer 1

比较函数（在本例中为>）获取两个参数（要比较的两个元素）。参数pathLength在比较之前将通过关键函数 ( )。您可以使用TRACE查看调用函数的内容。例如：

(trace >)
;=> (>)
(sort (list 4 5 1) #'>)
;  0: (> 5 4)
;  0: > returned T
;  0: (> 1 4)
;  0: > returned NIL
;=> (5 4 1)
(trace 1+)
;=> (1+)
(sort (list 4 5 1) #'> :key #'1+)
;  0: (1+ 5)
;  0: 1+ returned 6
;  0: (1+ 4)
;  0: 1+ returned 5
;  0: (> 6 5)
;  0: > returned T
;  0: (1+ 1)
;  0: 1+ returned 2
;  0: (1+ 4)
;  0: 1+ returned 5
;  0: (> 2 5)
;  0: > returned NIL
;=> (5 4 1)
(untrace > 1+)
;=> T

关于您的代码的一些评论。

1. 在 Lisps 中，函数和变量的命名约定是全部使用小写字母，单词之间带有破折号。所以add-to-queue代替AddtoQueue. 名称（符号）通常会自动转换为大写（并在注释等中如此编写），但在编写实际代码时应使用小写。
2. 您不应该将右括号放在自己的行上。使用换行符和缩进来显示程序的结构。
3. 局部变量应该使用LET而不是定义SETQ。
4. 由于CONDinADD-TO-QUEUE仅将 if 与符号进行比较METHOD，EQ因此CASE更适合该任务。
5. 您PATH-LENGTH正在使用变量QUEUE，该变量是 的本地变量ADD-TO-QUEUE。您需要使用 将该函数移动到同一范围内FLET。
6. 它还使用名为TERMINALand的变量COORDS，这两个函数中似乎都不存在该变量。如果这些是全局（特殊）变量（应使用DEFVAR或DEFPARAMETER定义），则应在名称周围添加耳罩（星号）以表明：*TERMINAL*, *COORDS*。

如果没有完整的代码，我无法对此进行测试，但代码应该如下所示：

(defun add-to-queue (queue method)
  (flet ((path-length (point)
           (let* ((x (1- (length queue)))
                  ;; It's better to use FIRST and SECOND instead of CAR and
                  ;; CADR when dealing with lists.
                  (temp (calc-lists (second (assoc (car point) *coords*))
                                    (second (assoc *terminal* *coords*))
                                    'sub))
                  (y (+ (first temp) (second temp))))
             (+ x y))))
    (case method
      (DFS
       ;; Consider using full words for function names. So
       ;; FIND-CHARACTER, assuming that's what CH means.
       (append (grow-path (car queue)
                          (find-ch (caar queue)))
               (cdr queue)))
      (BFS
       (append (cdr queue)
               (grow-path (car queue)
                          (find-ch (caar queue)))))
      (A
       (sort (append (cdr queue)
                     (grow-path (car queue)
                                (find-ch (caar queue))))
             #'> :key #'path-length))
      ;; You could use `ECASE` to automatically signal an error
      ;; if METHOD doesn't match any of the cases.
      (otherwise "not implemented"))))