0

我正在尝试开发一个简单的函数来返回 Lisp 中的最小值和最大值。到目前为止，我有适用于单个 Lisp 的基本解决方案，这是代码

(defun get-smallest-large (lst &optional (smallest 0) (largest 0))
  (setf smallest (first lst))
  (setf largest 0)
  (dolist (nxt lst)
    (if (< nxt smallest)
        (setf smallest nxt)
        (if (> nxt largest)
            (setf largest nxt))))
  (cons smallest largest))

这就像：

(defun get-smallest-large '(1 2 -1 3))
= (-1 . 3)

现在，我一生都无法弄清楚如何更改此解决方案以处理嵌套列表，例如，我输入了以下内容：

(defun get-smallest-large '(5 (-2 20 (3)) -6 (-7 13)))
= (-7 . 20)

我该怎么办？

4

4 回答 4

3

这是您可以处理它的一种方法：当您递归到子列表时，处理返回值，就好像它们也是外部列表的元素一样。示例（在我的“母语”Scheme 中；需要SRFI 26）：

(define (min-max x (min #f) (max #f))
  (cond ((null? x) (if min (values min max) (values)))
        ((cons? x) (call-with-values (cut min-max (car x) min max)
                                     (cut min-max (cdr x) <...>)))
        (else (values (if (and min (< min x)) min x)
                      (if (and max (> max x)) max x)))))

这是相同的 Common Lisp 的直接翻译，我的意思是它根本不是惯用的 CL，而是为不熟悉 Scheme 的 CL 程序员提供的，以了解 Scheme 代码的作用。特别是，Scheme 对正确尾递归的要求仍然成立，即使 CL 没有提供。

(defun min-max (x &optional min max)
  (cond ((null x) (if min (values min max) (values)))
        ((consp x)
         (multiple-value-call #'min-max (cdr x) (min-max (car x) min max)))
        (t (values (if (and min (< min x)) min x)
                   (if (and max (> max x)) max x)))))
于 2013-11-15T03:45:26.820 回答
1

这是一个避免递归并使用一个不错的 Common Lisp 库的版本iterate：

(ql:quickload :iterate)
(use-package :iterate)

(defun minmax (tree)
  (iter
    (with head := tree)
    (with stack := nil)
    (while (or head stack))
    (cond
      ((and (null head) stack)
       (setf head (cdr (pop stack))))
      ((consp (car head))
       (push head stack)
       (setf head (car head)))
      ((car head)
       (minimize (car head) :into min)
       (maximize (car head) :into max)
       (setf head (cdr head))))
    (finally (return (values min max)))))

对于非常大、深度嵌套的树，这将是一种首选方式，它以一些复杂性和 O(log n) 空间（用于回溯）来换取可伸缩性（此处建议的其他版本将无法在足够大的树上执行，其中限制将是 Lisp 实现为每个线程分配给此函数堆栈的内存。）

然而，递归版本的好处可能是原则上更容易使其并行运行多个计算。

然后使用一些宏观魔术，您可以隐藏原始minmax函数的无趣位（那些只处理迭代树的位）：

(defmacro-clause (FOR var IN-TREE tree)
  "Iterates over TREE in depth-first order"
  (let ((stack (gensym)) (head (gensym)))
    `(progn
       (with ,head := ,tree)
       (with ,stack := ,nil)
       (with ,var := ,nil)
       (while (or ,head ,stack))
       (cond
         ((and (null ,head) ,stack)
          (setf ,head (cdr (pop ,stack)))
          (next-iteration))
         ((consp (car ,head))
          (push ,head ,stack)
          (setf ,head (car ,head))
          (next-iteration)))
       (setf ,var (car ,head) ,head (cdr ,head)))))

(defun minmax (tree)
  (iter
    (for leaf :in-tree tree)
    (minimize leaf :into min)
    (maximize leaf :into max)
    (finally (return (values min max)))))

并且具有更精简的功能，仅显示重要部分。

这是使用lparallel库的算法的并行版本：

(ql:quickload :lparallel)
(setf lparallel:*kernel* (lparallel:make-kernel 128))

(lparallel:defpun pminmax (tree &optional min max)
  (labels ((%min (&rest numbers)
             (iter (for i :in numbers) (when (numberp i) (minimize i))))
           (%max (&rest numbers)
             (iter (for i :in numbers) (when (numberp i) (maximize i)))))
    (cond
      ((null tree) (cons min max))
      ((consp (car tree))
       (lparallel:plet
           ((head (pminmax (car tree) min max))
            (tail (pminmax (cdr tree) min max)))
         (cons (%min (car head) (car tail) min)
               (%max (cdr head) (cdr tail) max))))
      (t (destructuring-bind (new-min . new-max)
             (pminmax (cdr tree) min max)
           (cons (%min (car tree) new-min min)
                 (%max (car tree) new-max max)))))))

不幸的是，lparallel还没有实现 for 的替代方案multiple-value-bind，所以我们不得不将结果合并到一个 cons 单元格中，但是如果有一些持久性，就有可能实现上述宏的并行版本并摆脱这个不幸的限制（即作为练习留给读者）。

于 2013-11-17T17:22:28.047 回答
1

您的代码假定列表的所有元素都是数字。但是，如果您有一个嵌套列表，则该列表可以包含数字列表或数字列表列表等。

您的列表处理循环必须检查每个元素的类型并相应地进行处理。

如果您看到一个列表，您希望进行递归调用以get-smallest-large仅从该列表中获取最小值和最大值。在递归调用中，您传递了这两个额外的参数，以便该函数不会返回比您已经看到的更小的最大值或更大的最小值。

由于返回值是一个缺点，递归调用可能看起来像这样：

(destructuring-bind (sm . la) (get-smallest-large smallest largest)
  (setf smallest sm largest la))

在 Common Lisp 中，函数可以返回多个值；返回一对数字作为 cons 的代码看起来像是来自 Lisp 方言的快速而肮脏的代码端口，没有多值支持。

这意味着我们可以返回（实际上返回两个值） ，而不是返回(cons smallest largest)（返回单个值，它是一个包含两个数字的单元格）。(values smallest largest)使用这些值的递归调用然后浓缩为：

(multiple-value-setq (smallest largest) (get-smallest-large smallest largest))

setf函数开头的两次调用会破坏递归的正确性。如果给定函数smallest并且largest输入值，它必须尊重这些值，而不是简单地通过从列表结构中获取任意值来覆盖它们。该代码还有另一个问题，它假定这(first lst)是一个数字。它可能是一个子列表！还有一个问题：列表可能是空的！！！

我建议这样做：

(defun get-smallest-large (list &optional smallest largest)
  ;; 
 )

也就是说， defaultsmallest和largestto nil，并nil在其余代码中处理为表示“未知的最小值或最大值”。例如：

 ;; the number we are looking at is smallest so far, if we have not
 ;; seen any number before, or if it is smaller than the smallest one we have
 ;; seen so far.
 (if (or (null smallest) (< nxt smallest))
    (setf smallest nxt))

这也将修复另一个错误。想想如果在一个空列表上调用你的函数应该返回什么。当然不是(0 . 0)：零不会出现在空列表中。在这种情况下返回的合理表示是(nil . nil)表示最低和最高数字未知。

于 2013-11-15T03:23:11.133 回答
0

使用众所周知的函数 flatten 首先将嵌套列表展平，然后再对其应用自己的 minimax 函数。

(defun flatten (x)
  (cond ((null x) nil)
        ((atom x) (list x))
        (t (append (flatten (car x))
                   (flatten (cdr x))))))

然后申请：

(get-smallest-large (flatten '(5 (-2 20 (3)) -6 (-7 13))))
;; returns: (-7 . 20)

它有效，因为

(flatten '(5 (-2 20 (3)) -6 (-7 13)))
;; returns: (5 -2 20 3 -6 -7 13)

由于列表是平的，您可以在其上应用您的原始功能。

使用 flatten，您可以编写一个通用get-smallest-large*函数，该函数适用于嵌套列表和平面列表：

(defun get-smallest-large* (lst &optional (smallest 0) (largest 0))
  (get-smallest-large (flatten lst) smallest largest))

;; now you call on any lists - flat or nested:
(get-smallest-large* '(5 (-2 20 (3)) -6 (-7 13)))

如果列表很大，您必须考虑生成器列表和生成器展平。这是在这里解释https://www.cs.northwestern.edu/academics/courses/325/readings/list-gen.php

于 2018-05-20T08:54:47.273 回答