list - 仅使用构造函数中的列表查找 Lisp 列表中的最小数字？

Question

我的教授在期中考试时给了我们这个难题，除非我没有看错，否则这是一个看似简单的非常棘手的问题。

7. Write a lisp function f that finds the minimum value of a list. Assume that the list contains numbers only. For example (f '(3 2 5 4 9 5)) returns 2.

这是我目前所拥有的:

(defun f (L)
 (cond ((null (cdr L))(car L))    ; <-- I think my break case is wrong, too.
       ((< (car L) (car (cdr L))) (rotatef((car L) (car(cdr L)))))
 (f(cdr L))
 )
)

编译器告诉我，我对 rotatef 的使用很糟糕。

我的逻辑是不断的和car(cdr L)交换最小的元素，总是有car(L)作为最小的元素。然后递归调用 cdr 直到只有那是我能想到的唯一方法。奇怪的是，他从未在我们的笔记中提到 rotatef，所以我想我做的很糟糕。

伟大的 Lisp 大神们，你能帮帮我吗？你是我唯一的希望。

Answer 1

• 你应该计算一个最小值，所以让我们调用函数minimum
• L 作为变量名可以替换为 list
• 改进缩进和括号

然后它看起来像这样:

(defun minimum (list)
 (cond ((null (cdr list))
        (car list))    ; <-- I think my break case is wrong, too.
       ((< (car list) (car (cdr list)))
        (rotatef ((car list)
                  (car (cdr list)))))
       (minimum
        (cdr list))))

现在你可以摆脱CAR，CDR:

(defun minimum (list)
 (cond ((null (rest list))
        (first list))    ; <-- I think my break case is wrong, too.
       ((< (first list) (second list))
        (rotatef ((first list)
                  (second list))))
       (minimum
        (rest list))))

最后一个 cond 子句中的最小值没有意义，因为它需要一个带有 bool 值的列表:

(defun minimum (list)
 (cond ((null (rest list))
        (first list))    ; <-- I think my break case is wrong, too.
       ((< (first list) (second list))
        (rotatef ((first list)
                  (second list))))
       (t (minimum (rest list)))))

ROTATEF 有多少参数？ ((foo) (bar)) 在 Lisp 中不是有用的语法，因为你不能在一堆 Lisp 形式周围加上括号。

(defun minimum (list)
 (cond ((null (rest list))
        (first list))    ; <-- I think my break case is wrong, too.
       ((< (first list) (second list))
        (rotatef (first list)
                 (second list)))
       (t
        (minimum (rest list)))))

什么是空列表？

(defun minimum (list)
 (cond ((null list)
        nil)
       ((null (rest list))
        (first list))
       ((< (first list) (second list))
        (rotatef (first list)
                 (second list)))
       (t
        (minimum (rest list)))))

ROTATEF 没有意义，因为它不返回最小值。

(defun minimum (list)
 (cond ((null list)
        nil)
       ((null (rest list))
        (first list))
       ((< (first list) (second list))
        (minimum (cons (first list)
                       (rest (rest list)))))
       (t
        (minimum (rest list)))))

最后添加一个简短的文档字符串。

(defun minimum (list)
 "recursive function to return the minimum value of a list of numbers"
 (cond ((null list)
        nil)
       ((null (rest list))
        (first list))
       ((< (first list) (second list))
        (minimum (cons (first list)
                       (rest (rest list)))))
       (t
        (minimum (rest list)))))

解释:

(defun minimum (list)

 "recursive function to return the minimum value of a list of numbers"

 (cond

       ((null list)                      ; list is empty
        nil)

       ((null (rest list))               ; only one element
        (first list))

       ((< (first list) (second list))   ; if first element is smaller than second
        (minimum (cons (first list)      ; call minimum without second element 
                       (rest (rest list)))))

       (t                                ; second is equal or smaller
        (minimum (rest list)))))         ; call minimum without first element

现在我们也必须测试它:

CL-USER 24 > (let ((lists '(()
                            (1)
                            (1 2)
                            (2 1)
                            (3 2 1 0)
                            (1 2 3)
                            (3 4 2 1 1)
                            (1 1 12 -1 4 2))))
               (mapcar #'minimum lists))

(NIL 1 1 1 0 1 1 -1)