リスト遊び 4-5 集合

前回
リスト遊び 4-4 再帰とリスト - by shigemk2

久々だね。このネタ。
ある対象データがある集合の要素であるかを判定する関数memqと、
ある対象リストがある集合の部分集合であるかを判定する関数subsetを作成する。

(memq 3 '(1 2 3))
=> t
(memq 'dog '(pig rat))
=> nil

(defun memq (x set)
  (cond
   ((null set) nil)
   ((eq x (car set)) t)
   ;; マッチしなかったら再帰を使ってxとリストのcdrを評価する
   (t (memq x (cdr set)))))
(memq 3 '(1 2 3))
t
(memq 'dog '(pig rat))
nil

;; リストが部分集合であるかどうかをサーチする関数
;; さっき作ったmemq関数を利用して、set1の全てのcarがset2に
;; マッチすればtを、1コでもマッチしなければnilを返す
(defun subset (set1 set2)
  (cond((null set1) t)
       ((null (memq (car set1) set2)) nil)
       (t (subset (cdr set1) set2))))
subset
(subset '(1 2 3) '(1 2 3 4))
t
(subset '(1 2 3) '(2 3 4))
nil
(subset '(dog pig rat) '(dog pig rat guineapig))
t

;; 2回nullを使っているのが気にくわないなら、
;; andを使って書き直すのもよいかと。
(defun subset (set1 set2)
  (cond
   ((null set1) t)
   (t (and (memq (car set1) set2)
	    (subset (cdr set1) set2)))))
subset
(subset '(1 2 3) '(1 2 3 4))
t
(subset '(dog pig rat) '(dog guineapig rat))
nil

リスト遊び―Emacsで学ぶLispの世界 (ASCII SOFTWARE SCIENCE Language)