1

2 つのリストを引数として取り、繰り返しなしで 2 つの和集合であるリストを返す和集合関数を Lisp で記述する必要があります。順序は入力リストの順序と一致する必要があります

例: 入力が '(abc) および '(ecd) の場合、結果は '(abced) になります。

これが私がこれまでに持っているものです

(defun stable-union (x y)
  (cond
   ((null x) y)
   ((null y) x))
  (do ((i y (cdr i))
       (lst3 x (append lst3 
                       (cond
                        ((listp i) 
                         ((null (member (car i) lst3)) (cons (car i) nil) nil))
                        (t (null (member i lst3)) (cons i nil) nil)))))
        ((null (cdr i)) lst3)))

私のエラーは、セグメント (null (member (car i) lst3)) を持つ「不正な関数オブジェクト」があることです。

アドバイス？

4

4 に答える 4

1

あなたはあなたの括弧をすべてごちゃ混ぜにしました：

(defun stable-union (x y)
  (cond
   ((null x) y)
   ((null y) x)  )     END OF COND form - has no effect

  (do ((i y (cdr i))
      ^^
       (lst3 x (append lst3 
                       (cond
                        ((listp i) 
                         (  (null (member (car i) lst3)) 
                         ^^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ called as a function
                             (cons (car i) nil)           with two arguments
                             nil  ) )
                                 ^^ 
                        (t                         NEXT 3 forms have no effect
                           (null (member i lst3))
                           (cons i nil)
                           nil           )))) )
                                             ^^
        ((null (cdr i)) lst3)))

おそらく意図したとおりのコードです。括弧を修正し、必要に応じていくつかifの s を追加しています。

(defun stable-union (x y)
  (cond
   ((null x) y)
   ((null y) x)
   (t
    (do ((i y (cdr i))
         (lst3 x (append lst3 
                   (cond
                     ((listp i) 
                       (if (null (member (car i) lst3))
                           (cons (car i) nil)
                           nil))
                     (t 
                       (if (null (member i lst3))
                           (cons i nil)
                           nil))))))
        ((null (cdr i)) lst3)))))

このコードにはまだ問題があります。ロジックdoが間違っていますy。要素が 1 つしか含まれていない場合、最初の要素をスキップします。そしてappend、必要かどうかにかかわらず、常に電話をかけます。を呼び出す(append lst3 nil)と、 のトップレベルのコンス セルのコピーが作成されることに注意してくださいlst3。

あなたが持っているような長いステートメントは、通常、のローカル変数のdo更新フォーム内ではなく、本体に配置されます。do

ただし、必要に応じて、より特殊な形式の を使用できますdo。ここでは を使用するのが自然dolistです。メンバーシップ テストにハッシュ テーブルを使用することに関する "wvxvw" のリードに従って、次のように記述します。

(defun stable-union (a b &aux (z (list nil)))
  (let ((h (make-hash-table))
        (p z))
    (dolist (i a)
      (unless (gethash i h)
        (setf (cdr p) (list i) p (cdr p))
        (setf (gethash i h) t)))
    (dolist (i b (cdr z))
      (unless (gethash i h)
        (setf (cdr p) (list i) p (cdr p))
        (setf (gethash i h) t)))))

私が「head-sentinel」(シングルトン リストに事前に初期化された変数) と呼んでいる手法を使用すると、余分なセルzを 1 つ割り当てる代償を払って、トップダウン リスト構築のコードを大幅に簡素化できます。cons

于 2012-10-13T19:57:08.277 に答える
1

エラーは、評価の結果を実行しようとしているためです(null (member (car i) lst3))。cond式で、iがリストの場合、式を評価しようとします

((null (member (car i) lst3)) (cons (car i) nil) nil))

そして結果を返します。式の最初の要素は関数でなければなりませんが、

(null (member (car i) lst3))

ブール値を返す予定です。したがって、失敗。コードの構造には注意が必要です。あなたが見逃したのは、そこに内部condが必要だということです。

ちなみに、これを再帰的に行うと、よりクリーンな関数になります。

私はLisperではなくSchemerですが、少し考えてみました。再帰的な実装のスケルトンは次のとおりです。

(defun stable-union (x y)
  (cond
    ((null x) y)
    ((null y) x)
    ((listp y)
     (cond 
       ((member (car y) x) (stable-union ??? (???))) 
       (t (stable-union (append x (??? (???))) (cdr y)))))
    ((not (member y x)) (append x (list y)))
    (t x)))

(それを見つけてくれたウィル・ネスのおかげで、最後から2番目の行の単純なタイプミスを修正するために編集されました)

于 2012-10-11T23:46:57.303 に答える
0

から始めたdoので、再帰的な解決策はさらに悪いので、次のことができたはずです。

(defun union-stable (list-a list-b)
  (do ((i list-b (cdr i))
       filtered back-ref)
      ((null i) (append list-a back-ref))
    (unless (member (car i) list-a)
      (if back-ref
          (setf (cdr filtered) (list (car i))
                filtered (cdr filtered))
          (setf back-ref (list (car i))
                filtered back-ref)))))

これはまだ 2 次時間であり、最初のリストに重複がある場合、または 2 番目のリストに最初のリストにない重複がある場合、それらはそのまま残ります。この関数を「ユニオン」と呼ぶのがどれほど公平かはわかりませんが、それらを統合しようとする前に、リストに重複がある場合はどうするかを定義する必要があります。

これは、単に運動するのではなく、結果に関心がある場合に実行したかもしれないことです。要素が入力リストで繰り返される場合でも、要素が一意であることを保証することに注意してください。

(defun union-stable-hash (list-a list-b)
  (loop for c = (car (if list-a list-a list-b))
     with back-ref
     with hash = (make-hash-table)
     for key = (gethash c hash)
     with result
     do (unless key
          (if back-ref
              (setf (cdr result) (list c)
                    result (cdr result))
              (when (or list-a list-b)
                (setf back-ref (list c)
                      result back-ref)))
          (setf (gethash c hash) t))
     do (if list-a (setf list-a (cdr list-a))
            (setf list-b (cdr list-b)))
     do (unless (or list-a list-b)
          (return back-ref))))
于 2012-10-12T16:54:23.967 に答える