読者です 読者をやめる 読者になる 読者になる

by shigemk2

当面は技術的なことしか書かない

リスト遊び 7-5 while と 再帰

読書ノート

前回
リスト遊び 7-4 catch と throw - by shigemk2

いつぞやのmemq*を、catch throw while を使って書き換えてみる。
いつぞやのやつ
リスト遊び 5-4 集合* - by shigemk2

(defun memq* (x set)
  (catch 'loop
    (while set
      (cond
       ;; リストの中にリストがあったら
       ((consp (car set))
	(let ((s (car set)))
	(while s
	  (cond
	   ((eq x (car s))
	    (throw 'loop t)))
	  (setq s (cdr s)))))
       ;; リストの中にリストが無かったら
       ;; x がリストの中に存在していたら
       ((eq x (car set))
	(throw 'loop t)))
      (setq set (cdr set)))))
memq*
(memq* 2 '(1 2 3))
t
(memq* 2 '(1 (1 2 3) 3))
t
(memq* 2 '(1 (1 (1 2 3) 3) 3))
nil

上記だと、リストのリストのリストではうまくいかない。

(defun memq* (x set)
  (catch 'loop
    (while set
      (cond
       ((and (consp (car set))
	     (memq* x (car set)))
	(throw 'loop t))
       ((eq x (car set))
	(throw 'loop t))
      ((eq x (car set))
       (throw 'loop t)))
    (setq set (cdr set)))))
memq*
(memq* 2 '(1 2 3))
t
(memq* 2 '(1 (1 2 3) 3))
t
(memq* 2 '(1 (1 (1 2 3) 3) 3))
t

whileと再帰を上手く組み合わせるとうまくいく。

単純な繰り返しは、速度を変えてwhileで実現する
再帰的なアルゴリズムは、汎用性を考えて再帰で実現する。

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

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