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 コードが何をするかを理解するために提示されていることを意味します。特に、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

あなたのコードは、リストのすべての要素が数値であると想定しています。ただし、ネストされたリストがある場合、リストには数値のリストや数値のリストのリストなどを含めることができます。

リスト処理ループは、各要素のタイプを検査し、それに応じて処理する必要があります。

リストが表示された場合は、 を再帰的に呼び出して、get-smallest-largeそのリストから最小値と最大値を取得します。再帰呼び出しでは、これらの追加の 2 つのパラメーターを渡します。これにより、関数は、既に見たものよりも小さい最大値や大きい最小値を返さなくなります。

戻り値はコンスであるため、再帰呼び出しは次のようになります。

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

Common Lisp では、関数は複数の値を返すことができます。コンスとして数値のペアを返すコードは、複数の値をサポートしていない Lisp 方言からのコードの迅速かつ汚いポートのように見えます。

これは、返す(cons smallest largest)(2 つの数値を保持するセルである単一の値を返す) 代わりに、返す(values smallest largest)(実際には 2 つの値を返す) ことができることを意味します。値を使用する再帰呼び出しは、次のように要約されます。

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

関数の先頭にある2 つのsetf呼び出しは、再帰の正確性を損ないます。関数が指定され、入力時に値が指定されている場合、関数はsmallestそれらlargestの値を尊重する必要があり、リスト構造から任意の値を取得して単純に上書きしてはなりません。そのコードには、それが数値であると仮定するという別の問題もあります(first lst)。それはサブリストかもしれません！さらに別の問題: リストが空になる可能性があります!!!

次のようにすることをお勧めします。

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

つまり、 defaultsmallestおよびlargesttonilであり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 を使用して、ネストされたリストを平坦化してから、独自のミニマックス関数を適用します。

(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 に答える