Минимальный элемент в дереве

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

Ваш 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 2

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

Answer 3

Использование 99999 - это действительно взлом (не хороший вид хаков), пожалуйста, не делайте этого. Использование :infinity немного лучше, но все же, хотите ли вы, чтобы результат был :infinity при предоставлении пустого списка? Подход loop лучше, но когда список пуст, минимизация возвращает 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 делает.