SICP 読み (102) 3.3.1 可変リスト構造

合間に検討だとなかなか微妙。パラで数本走ってる状態ってのはあまり良くない。どっかで集中して検討する時間をなんとかして取らねば、な今日この頃。

問題 3.17

とりあえず試験を書いてみた。

#!/usr/bin/env gosh

(use test.unit)
(require "3.17")

(define-test-suite "3.17"

  ("count-pairs test"
   ("normal list"
    (let ((l (list 'a 'b 'c)))
      (assert-equal 3 (count-pairs l))
      )
    )

   ("old count-pairs returns 4"
    (let ((l1 (list 'a)))
      (let ((l2 (cons l1 l1)))
	(let ((l (cons 'b l2)))
	  (assert-equal 3 (count-pairs l))
	  )
	)
      )
    )

   ("old count-pairs returns 7"
    (let ((l1 (list 'a)))
      (let ((l2 (cons l1 l1)))
	(let ((l (cons l2 l2)))
	  (assert-equal 3 (count-pairs l))
	  )
	)
      )
    )

   )
  )

全部 3 にならなきゃ NG。で、末尾再帰な繰り返しで何とかならんか、と思ってたんですが、car 側と cdr 側なソレをしなきゃ、な世界だとすると最初は再帰で考えた方が楽そうなカンジ。

検討

上記試験のパターンで検討してみる。まず_補助のデータ構造_を作らなければならないので、その方法を。
まず、一番ノーマルな

   (let ((l (list 'a 'b 'c)))

なソレから考えてみる。パースを終える条件としては

(not (pair? (car x)))
(null? (cdr x))

になるのか。いや、(not (pair? (car x))) はパースを終えるというよりは、_補助のデータ構造_を作らない、と言った方が良さげ。これを前提にすると

l を追加
(car l) はペアではないのでスルー
(cdr l) はペアなので追加
(cdr (car l)) はペアではないのでスルー
(cdr (cdr l)) はペアなので追加
(cdr (cdr (car l))) はペアではないのでスルー
(cdr (cdr (cdr l))) は終端なので処理終了

になるんか。最初は「l はぺアなので追加」という処理の方が良い??

次は 4 つ要素があると誤解される以下の構造。

   (let ((l1 (list 'a)))
     (let ((l2 (cons l1 l1)))
       (let ((l (cons 'b l2)))

l はペアなので追加
(car l) はペアでないのでスルー
(cdr l) はペアなので追加
(cdr (car l)) はペアなので追加
(cdr (car (cdr l))) は終端なので終了
(cdr (cdr l)) はペアなので追加 (がしかし、2 コ前で追加済み)
(cdr (cdr (cdr l))) は終端なので終了

うーん。これを何とか手続きに置き換えないと答えにならないんだよね。(困

てか、mutator って使い方微妙。代入って概念が入ってきてるんで C とかソレ系の考え方で良い、とゆーのは承知してるんですが ...

で、頭をヒネった挙句にとりあえず pair? なソレを単純に印字してみた。

(define (count-pairs x)
  (define (display-line x)
    (newline)
    (display x))
  (if (pair? x)
      (begin (display-line x)
	     (count-pairs (car x))
	     (count-pairs (cdr x))))
  )

これでペアの列挙ができているはず。

gosh> (define l1 (list 'b))
l1
gosh> (define l2 (cons l1 l1))
l2
gosh> (define l (cons 'a l2))
l
gosh> (count-pairs l)

(a (b) b)
((b) b)
(b)
(b)#<undef>
gosh> (define l '(a b c))
l
gosh> (count-pairs l)

(a b c)
(b c)
(c)#<undef>
gosh>

あとは、pair? だから検査用のデータ構造に set-cdr! してけば OK なはずなんですが ...

中断後

列挙はできているようなんですが、これをどうやってフィルタして accumulate すれば良いのやら。とは言え、蓄積されている要素と eq? なソレは却下すりゃ良いだけなんでしょうが、それを具体的にどうすりゃ良いやら。

ガワは以下なカンジでしょうか

(define (count-pairs x)
  (define (set-list! l x)
    )

  (define (count-pairs-iter x l)
    (if (pair? x)
	(begin (set-list! l x)
	       (count-pairs-iter (car x) l)
	       (count-pairs-iter (cdr x) l))
	(if (null? x)
	    l)))

  (length (count-pairs-iter x (cons x '())))
  )

で、set-list! でハマりました。まず

空リストに set-cdr! できん

というのがトホホな第一感。(cdr l) が null になるまで (car l) と x を比較しつつ、処理終了なタイミングは l が null になった時点。あ、処理終了なタイミングか。

l が null でオワり
(car l) と x が eq? だったらオワり

上記の条件をパスしつつ、(cdr l) が null じゃなかったら (cdr l) を渡して再帰。そうでなければ set-cdr! すれば良い、という事みたい。(??

一応上記の試験をパスした実装を以下に。なんとかする余地が大あり。

(define (count-pairs x)
  (define (set-list! l x)
    (if (not (null? l))
	(if (not (eq? (car l) x))
	    (if (not (null? (cdr l)))
		(set-list! (cdr l) x)
		(set-cdr! l (cons x '())))))
    )

  (define (count-pairs-iter x l)
    (if (pair? x)
	(begin (set-list! l x)
	       (count-pairs-iter (car x) l)
	       (count-pairs-iter (cdr x) l))
	(if (null? x)
	    l)))

  (length (count-pairs-iter x (cons x '())))
  )

うーん。微妙。