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. 因为 ADD-TO-QUEUE 中的 COND 仅比较 METHOD 是否为 EQ 到一个符号, CASE会更适合这项任务。
5. 您的PATH-LENGTH 正在使用变量QUEUE，它是ADD-TO-QUEUE 的本地变量。您需要使用 FLET 将函数移动到同一范围内.
6. 它还使用了名为 TERMINAL 和 COORDS 的变量，这两个函数中似乎都不存在。如果这些是全局(特殊)变量(应使用 DEFVAR or 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"))))