树中的最小元素

Question

我想在 Lisp 中的非线性列表（编辑：树）中找到最小元素（在任何级别）。我写了类似的东西：

(defun minimum (l)
  (cond
    ((null l) 99999)
    ((atom (car l)) (min (minimum (cdr l)) 99999))
    ((numberp (car l)) (min (car l) (minimum (cdr l))))
    (T (min (minimum (cdr l)) (minimum (Car l))))))

但是，它不起作用（因为非数字原子的条件，我猜...）。有没有人知道如何修复此代码？提前致谢。

Answer 1

(defun minimum (tree)
    (loop for item in tree
         if (consp item) minimize (minimum item)
         else if (numberp item) minimize item))

Answer 2

你的 numberp 案例永远不会执行，因为 atom 案例首先被测试，数字是原子。所以每个数字都被 99999 替换。将 numberp 的情况放在第一位。

您的代码的另一个问题是，如果树中的最小数字大于 99999，它不会找到最小的数字。要在不过多更改代码的情况下修复它，您需要自己的 min 支持无穷大的表示：

(defun inf-min (a b)
     (cond ((eq a :infinity) b)
           ((eq b :infinity) a)
           ((< a b) a)
           (t b)))

然后，将 min 替换为 inf-min，将 99999 替换为 :infinity。

Answer 3

使用 99999 确实是一种 hack（不是好的 hack），请不要这样做。使用 :infinity 稍微好一点，但是，当给出一个空列表时，你希望结果是 :infinity 吗？ loop 方法更好，但是当列表为空时，最小化 returns 0，这通常不是我们想要的。

对于零值未定义最小函数，因此我将定义一个 tree-min 函数，当树不包含任何数字时，其结果为 nil。像这样：

(defun tree-min (tree)
  (typecase tree
    ;; base case with numbers
    (number tree)

    ;; string are sequences too, but don't iterate over them.
    (string nil) 

    ;; vectors and lists
    (sequence (reduce (lambda (m e)
                        (let ((em (tree-min e)))
                          (or (and m em (min em m)) ; Eminem?
                              em)))
                      tree
                      :initial-value nil))))

该函数会自动跳过任何非数字元素。以下是一些示例：

(tree-min #(3 2 nil (2 1 -20) 100 20 ))
=> -20

(tree-min nil)
=> nil

(tree-min '(a 20))
=> 20

在实践中，您可以将此函数概括为采用像 extremum 那样的比较函数。

树中的最小元素

Minimum element in a tree

lisp

tree

common-lisp

minimum