2

宿題があり、次のことをする必要があります。

ツリーを引数として取り、ツリーに一意のノードのみが含まれるかどうかを示すnil / non-nil値を返す関数（つまり、ツリーに重複するノードがない）。

これまでに次のコードを記述しました。私はLispの初心者で、宿題を終える必要があります。これは私が実装しようとしている最初のソリューションです。しかし、コンパイルすると、次のエラーが発生します。関数の位置にはシンボルまたはラムダ式が含まれている必要があります：（FIRSTTREE）。

  (defun in (tree)
    (cond ((null tree)
           t)
          ((eq (first tree) (second tree))
           nil)
          ((listp (first tree))
           (or ((first tree) in  (second tree))
               ((first tree) in  (rest tree))))
          (t
           ((first tree) in (rest tree)))))

これが私の2回目の試みですが、これも機能していません。

(defun flatten (structure)
  (cond ((null structure) nil)
        ((atom structure) `(,structure))
        (t (mapcan #'flatten structure))))

(defun uniNodes (inList &optional (out t) (test 0))
  (cond ((null inList)
         out)
        ((zerop test)
         (uniNodes (flatten(cons (first inList) (rest inList))) out (+ test 1)))
        ((eq t (first out))
         (uniNodes (rest inList) (compare1 (first inList) (rest inList) (first out)) test))
        ((eq nil (first out))
         out)))

(defun compare1 (a list &optional (out t))
  (cond ((null list)
         out)
        ((equal a (first list))
         nil)
        (t
         (compare1 a (rest list) (first out)))))

洞察をお願いします。

4

2 に答える 2

1

テーブルにノードを集めて、ツリーを再帰的にトラバースすることをお勧めします。

(defun find-dupes (tree)
  (let ((table (make-hash-table)))
    (labels ((check-node (node)
               (when (consp node)
                 (when (gethash node table)
                   (return-from find-dupes node)) ; return the dupe
                 (setf (gethash node table) node) ; memorize the node
                 (check-node (car node))
                 (check-node (cdr node)))))
      (check-node tree))))

問題に合わせて上記のコードを変更する方法を理解する必要があります。

エラーについては、

Function position must contain a symbol or lambda expression: (FIRST TREE)

関数呼び出しを修正する必要があることを意味します

(A in B)

と

(in A B)

引数のサイズは2次式のようですが、2回目の試行の何が問題になっているのか説明しませんでした。

于 2012-11-28T18:30:02.510 に答える
0

ツリーがそれほど大きくない場合は、次の再帰的アプローチが適しています。

(defun tree-contains-duplicates-p (tree)
  (labels ((%tree-contains-duplicates-p (node table)
             (cond
               ((null node) t)
               ((consp node)
                ;; lists can't be same unless they have
                ;; same atoms, but having two `nil' lists
                ;; is a trivial case, which you want to ignore
                ;; probably
                (and (%tree-contains-duplicates-p (car node) table)
                     (%tree-contains-duplicates-p (cdr node) table)))
               (t (unless (gethash node table)
                    (setf (gethash node table) t))))))
    (not (%tree-contains-duplicates-p tree (make-hash-table)))))

それ以外の場合は、ループに展開して、ツリーをトラバースするために実行した最後のアクションを記録し、そこからリーフを再開したいと考えています。

これはうまくいくはずです：

(defun tree-contains-duplicates-p (tree)
  (loop with leaf = tree
     with stack = nil
     with table = (make-hash-table)
     while (or leaf stack)
     do (cond
          ((null leaf)
           (setq leaf (car stack) stack (cdr stack)))
          ((consp (car leaf))
           (when (cdr leaf)
             (setq stack (cons (cdr leaf) stack)))
           (setq leaf (car leaf)))
          (t (setq leaf (cdr leaf))))
       (when leaf
         (if (gethash (car leaf) table)
             (return t)
             (setf (gethash (car leaf) table) t)))))
于 2012-11-28T18:23:22.060 に答える