6

深くネストされたリストに埋め込むことができ、決して同じ場所にない特定の値を見つける必要があります。または同じ深さです。リストの 1 つの形式を次に示します。

(setq my-list '(((partnum . 1) (type (TEXT . plain)) (body (charset UTF-8))
                 (disposition nil) (transfer-encoding QUOTED-PRINTABLE))
                ((partnum . 2) (type (TEXT . html)) (body (charset UTF-8))
                 (disposition nil) (transfer-encoding QUOTED-PRINTABLE))))

次に、「charset」の値を取得する必要があります。あるとすれば最初のもの。この構成では、簡単です。

(car (cdr (cadr (third (car my-list)))))
   => UTF-8

しかし、これは「体」細胞がどこにあるかを正確に知っているときです.

次のようにmapcarを再帰的に使用しようとしました:

(defun search-rec (list)
  (mapcar
     (lambda (x)
       (if (listp x)
           (search-rec x)
         (message "OY %s" x)))
     list))

(wrong-type-argument listp 1)しかし、再帰が最初のコンスセルの最初のアトムにヒットすると、毎回エラーが発生します。私の質問は本当にそれが何であるかだと思います:

リストを検索するにはどうすればよいですか?

編集リストは次のようになり、「charset」はまだ（本体）にあり（それが唯一の定数であると言いました）、もはや見つかりません:(

(setq my-list '(((partnum . 1)
                (1.1 (type (TEXT . plain)) (body (charset UTF-8))
                     (disposition nil) (transfer-encoding 7BIT))
                (1.2 (type (TEXT . html)) (body (charset UTF-8))
                     (disposition nil) (transfer-encoding 7BIT))
                (type . alternative) (body (boundary e89a8fb2067eba300404c63c5f7f))
                (disposition nil) (transfer-encoding nil))
               ((partnum . 1.1) (type (TEXT . plain)) (body (charset UTF-8))
                (disposition nil) (transfer-encoding 7BIT))
               ((partnum . 1.2) (type (TEXT . html)) (body (charset UTF-8))
                (disposition nil) (transfer-encoding 7BIT))
               ((partnum . 2) (type (IMAGE . x-xpixmap)) (body (name ladybug.xpm))
                (disposition nil) (transfer-encoding BASE64))))

ここで編集して、IRL の例をいくつか示します。

    (setq my-list haystack-list)
    (setq my-needle (tree-assoc 'charset my-list))
    (message "
-------------\n
- my-list: %s\n
- my-needle: %s\n
-------------\n" my-list my-needle)

プロデュース:

  • my-list: ((TEXT plain (charset UTF-8) nil nil 7BIT 260 18 nil nil nil) (TEXT html (charset UTF-8) nil nil QUOTED-PRINTABLE 738 17 nil nil nil) 代替 (境界 e89a8fb1f8061a6be404c70a24a0) nil nil )

  • 私の針：nil

一方、次の場合：

(tree-assoc 'charset '((TEXT plain (charset UTF-8) nil nil 7BIT 260 18 nil nil nil)
(TEXT html (charset UTF-8) nil nil QUOTED-PRINTABLE 738 17 nil nil nil) 
alternative (boundary e89a8fb1f8061a6be404c70a24a0) nil nil))
  =>(charset UTF-8)

本当に、ここで何が起こっているのかわかりません。「この干し草の山リストは何ですか?」しかし、それは関連していますか？私はこの haystack-list のコピー (my-list) に取り組んでいるので、何が異なる結果をもたらすのでしょうか? リストの引用？みんな、私は本当に迷っています

NB (この動作 (直接評価では機能しますが、defun/let プロダクションの状況では機能しません) は、与えられたすべてのソリューションで発生しました)

編集:最初に見つかったリストを抽出し、そのリストから(検索ではなく)要素を抽出しました。私はより速く証明しました。もちろん、これは「私の要素は常に見つかった最初のリストにある」と言えるときです; みんなのおかげで、私はこれらすべてを通して多くのことを学びました.

4

4 に答える 4

8

Association Listsのツリー アナログが必要なようです。assoc指定されたキーをヘッドとして含むリスト要素を取得する関数の規則に従うと、ツリーで動作する assoc のバージョンが次のようになります。

(defun tree-assoc (key tree)
  (when (consp tree)
    (destructuring-bind (x . y)  tree
      (if (eql x key) tree
        (or (tree-assoc key x) (tree-assoc key y))))))

例：

(let ((my-list '(((partnum . 1)
                  (1.1 (type (TEXT . plain)) (body (charset UTF-8))
                   (disposition nil) (transfer-encoding 7BIT))
                  (1.2 (type (TEXT . html)) (body (charset UTF-8))
                   (disposition nil) (transfer-encoding 7BIT))
                  (type . alternative) (body (boundary e89a8fb2067eba300404c63c5f7f))
                  (disposition nil) (transfer-encoding nil))
                 ((partnum . 1.1) (type (TEXT . plain)) (body (charset UTF-8))
                  (disposition nil) (transfer-encoding 7BIT))
                 ((partnum . 1.2) (type (TEXT . html)) (body (charset UTF-8))
                  (disposition nil) (transfer-encoding 7BIT))
                 ((partnum . 2) (type (IMAGE . x-xpixmap)) (body (name ladybug.xpm))
                  (disposition nil) (transfer-encoding BASE64)))))
  (tree-assoc 'charset my-list))

=> (charset UTF-8)
于 2012-08-12T12:10:02.603 に答える
2

Rainer の答えが暗黙のうちに示しているように、あなたが直面している問題は、コンス セルの cdr がリストを指している可能性があるか、他の種類のオブジェクトを指している可能性があることです。あなたのsearch-rec関数は後者の可能性を防ぎません。

あなたが探しているもののElispバージョンは次のとおりです（完全にテストされていません;サンプルデータで動作します）：

(defun find-charset (l)
  (catch 'my-result
    (find-charset-do l)))

(defun find-charset-do (l)
  (when (and (consp l) 
             (listp (cdr l)))
    (if (and (eq (car l) 'charset)
             (symbolp (cadr l)))
        (throw 'my-result (cadr l))
      (dolist (e l)
        (find-charset-do e)))))
于 2012-08-12T02:06:32.677 に答える
2

それは、あなたが何をしたいのか、そしてリスト構造がどれほど類似しているかに少し依存します (つまり、常に HTML パーツのリストを持っていますか? 文字セットは常に body 要素内にありますか?)

最初のステップは次のとおりです。

(defun list-query (list-of-keys data)
  (let ((data data))
    (while (and data list-of-keys)
      (setq data (assoc (car list-of-keys) data))
      (setq list-of-keys (cdr list-of-keys)))
    data))

呼び出すと結果(list-query '(body charset) (car my-list))が得(charset UTF-8)られます。my-list をループして body リスト内の最初 (またはすべて) の文字セットを見つけるのは比較的簡単です。

于 2012-08-11T06:41:13.860 に答える
2

この問題に対する私の見解は次のとおりです。おそらく役に立つと思います。

(defun depth-first-search (tree searched &optional comparator)
  "TREE is the nested list of elements to search, SEARCHED
is the element to search for, COMPARATOR is the function used
to compare elements of the tree to the searched element, if
you don't provide any, then `equal' is used.
Returns a list of subscripts to be used with `nth' to find the
searched element. If the result is `nil', the list itself
is the searched element. If the result is not a list,
the `not-found' symbol, then the element was not found."
  (unless comparator (setq comparator #'equal))
  (let ((operations 'not-found))
    (labels ((%df-search
              (item ops)
              (if (funcall comparator item searched)
                  (setq operations (reverse ops))
                (let ((offset 0))
                  (when (consp item)
                    (dolist (i item)
                      (%df-search i (cons offset ops))
                      (unless (eq operations 'not-found)
                        (return))
                      (incf offset)))))))
      (%df-search tree nil)
      operations)))

(defun nth-repeat (subscripts tree)
  "Given the list of SUBSCRIPTS, will subsequently evaluate
`nth' with every subscript on the result of the previous evaluation
 such as to find the element in the TREE."
  (let ((result tree))
    (dolist (i subscripts result)
      (setq result (nth i result)))))

(nth-repeat 
 (depth-first-search '(1 (1 1 2) (1 1 1 3)) 3)
 '(1 (1 1 2) (1 1 1 3)))

使用する必要がありますclが、これは非常に一般的であるため、おそらく気付かないでしょう。ほとんどの場合、既に持っている可能性があります。

編集: OK、この方法で不適切なリストの最後の要素を完全に調べることを避けることができますが、これはそこでも検索できないことを意味します:

(defun depth-first-search (tree searched &optional comparator)
  "TREE is the nested list of elements to search, SEARCHED
is the element to search for, COMPARATOR is the function used
to compare elements of the tree to the searched element, if
you don't provide any, then `equal' is used.
Returns a list of subscripts to be used with `nth' to find the
searched element. If the result is `nil', the list itself
is the searched element. If the result is not a list,
the `not-found' symbol, then the element was not found."
  (unless comparator (setq comparator #'equal))
  (let ((operations 'not-found))
    (labels ((%df-search
              (item ops)
              (if (funcall comparator item searched)
                  (setq operations (reverse ops))
                (let ((offset 0))
                  (when (consp item)
                    (block outer
                      (maplist
                       (lambda (x)
                         (%df-search (car x) (cons offset ops))
                         (when (or (not (eq operations 'not-found))
                                   (not (listp (cdr x))))
                           (return-from outer))
                         (incf offset))
                       item)))))))
      (%df-search tree nil)
      operations)))

(defun nth-repeat (subscripts tree)
  "Given the list of SUBSCRIPTS, will subsequently evaluate
`nth' with every subscript on the result of the previous evaluation
 such as to fint the element in the TREE."
  (let ((result tree))
    (dolist (i subscripts result)
      (setq result (nth i result)))))

(defvar my-list '(((partnum . 1)
                   (1.1 (type (TEXT . plain)) (body (charset UTF-8))
                        (disposition nil) (transfer-encoding 7BIT))
                   (1.2 (type (TEXT . html)) (body (charset UTF-8))
                        (disposition nil) (transfer-encoding 7BIT))
                   (type . alternative) (body (boundary e89a8fb2067eba300404c63c5f7f))
                   (disposition nil) (transfer-encoding nil))
                  ((partnum . 1.1) (type (TEXT . plain)) (body (charset UTF-8))
                   (disposition nil) (transfer-encoding 7BIT))
                  ((partnum . 1.2) (type (TEXT . html)) (body (charset UTF-8))
                   (disposition nil) (transfer-encoding 7BIT))
                  ((partnum . 2) (type (IMAGE . x-xpixmap)) (body (name ladybug.xpm))
                   (disposition nil) (transfer-encoding BASE64))))

(depth-first-search
 my-list '(charset UTF-8))              ; (0 1 2 1)

(nth-repeat
 (depth-first-search
  my-list '(charset UTF-8)) my-list)    ; (charset UTF-8)

おそらく、問題にアプローチする最善の方法ではありませんが、問題の要素に移動するcars とcdrs のシーケンスを記録するようにアルゴリズムを変更することで、より良い解決策が得られるでしょう。その場合、リストの「不適切な」部分を検索することもできます。しかし、ここでは遅すぎます :) おそらく明日です。

編集2：

(defun tree-to-proper-tree (tree)
  (cond
   ((null tree) nil)
   ((consp tree)
    (let ((head
           (if (consp (car tree))
               (tree-to-proper-tree (car tree))
             (car tree))))
    (cons head
          (tree-to-proper-tree (cdr tree)))))
   (t (list tree))))

(defun find-path-to (tree node &optional comparator)
  (unless comparator (setq comparator #'equal))
  (let ((operations 'not-found))
    (labels ((%df-search
              (item ops)
              (if (funcall comparator item node)
                  (setq operations (reverse ops))
                (when (consp item)
                      (%df-search (car item) (cons 'car ops))
                      (%df-search (cdr item) (cons 'cdr ops))))))
      (%df-search tree nil)
      operations)))

(defun c*r-path (path tree)
  (dolist (i path tree)
    (setq tree (funcall i tree))))

(defvar my-list '(((partnum . 1)
                   (1.1 (type (TEXT . plain)) (body (charset UTF-8))
                        (disposition nil) (transfer-encoding 7BIT))
                   (1.2 (type (TEXT . html)) (body (charset UTF-8))
                        (disposition nil) (transfer-encoding 7BIT))
                   (type . alternative) (body (boundary e89a8fb2067eba300404c63c5f7f))
                   (disposition nil) (transfer-encoding nil))
                  ((partnum . 1.1) (type (TEXT . plain)) (body (charset UTF-8))
                   (disposition nil) (transfer-encoding 7BIT))
                  ((partnum . 1.2) (type (TEXT . html)) (body (charset UTF-8))
                   (disposition nil) (transfer-encoding 7BIT))
                  ((partnum . 2) (type (IMAGE . x-xpixmap)) (body (name ladybug.xpm))
                   (disposition nil) (transfer-encoding BASE64))))

(tree-to-proper-tree my-list) ; the same lists as above but made into a proper lists

(c*r-path (find-path-to my-list 'UTF-8) my-list) ; UTF-8
(c*r-path (find-path-to my-list 'plain) my-list) ; plain

では、これtree-to-proper-treeを選択すると、すべての不適切なサブツリーが適切なツリーになるようにツリーが変換されます。または、 を使用して、検索した要素に到達する とのfind-path-toシーケンスを見つけ、そのシーケンスを評価して、その方法で記録された要素を返すことができます。carcdrc*r-path

この方法で同じノードの繰り返し発生を検索するのは非常に難しいことに注意してください。アイテムが見つかった回数をカウントするコンパレータ関数を提供する必要があります。

于 2012-08-11T09:06:15.413 に答える