リスト修行 (3) - yamanetoshi's diary

修行、と言いつつそれほどでもないあたり、自分に優しいな (駄目

そのゴ

_リストのn番目の要素を、好きなものにおきかえた、新しいリストをつくる手続きを、つくってください (第4回:二をもって一となすより)_って。

仕様としての前提を以下に列挙しときます。

引数は、リスト、置き換える要素番号、値の順で渡される
置き換える要素番号は 0 〜 (- (length リスト) 1) とする

リストをコピーする手続きを作ってみる。とりあえず再帰で。

(define (lcopy l)
  (if (null? l)
      '()
      (cons (car l) (lcopy (cdr l)))))

繰り返しにしようと思ったらどうするかね。

(define (lcopy l)
  (let f ((l l) (lst '()))
    (if (null? l)
	lst
	(f (cdr l) (append lst (list (car l)))))))

append シバり。

(define (lcopy l)
  (let f ((l l) (lst '()))
    (if (null? l)
	lst
	(let g ((lst lst))
	  (if (null? lst)
	      (f (cdr l) (list (car l)))
	      (cons (car lst) (g (cdr lst))))))))

うーん。ま、いいや。本題に入らんと。(を
例えば append シバリではない繰り返し版なら要素番号が分かってれば置き換えできるかな??

(define (rep l n c)
  (let f ((l l) (n n) (lst '()))
    (if (null? l)
	lst
	(f (cdr l)
	   (- n 1)
	   (append lst
		   (list (if (= n 0)
			     c
			     (car l))))))))

動いた。

gosh> (rep '(1 2 3) 0 3)
(3 2 3)
gosh> (rep '(1 2 3) 1 3)
(1 3 3)
gosh> (rep '(1 2 3) 1 '(4 5))
(1 (4 5) 3)
gosh>

そのロク

どんどんやってしまう。
次は_手続き、foldをつくってください(第4回:二をもって一となすより)_との事。

前節の lcopy の再帰版を使えば話が早そげ。

(define (lcopy l)
  (if (null? l)
      '()
      (cons (car l) (lcopy (cdr l)))))

こんな感じですか。

(define (fold kons knil list)
  (if (null? list)
      knil
      (kons (car list) (fold kons knil (cdr list)))))

試験をば。

gosh> (fold cons '() '(1 2 3 4 5))
(1 2 3 4 5)
gosh> (fold * 0 '(1 2 3 4 5))
0
gosh> (fold * 1 '(1 2 3 4 5))
120
gosh> (fold + 0 '(1 2 3 4 5))
15
gosh>

微妙にスッとぼけているのは愛嬌ってコトで。(とほほ
しかし語彙が増えてないよな、実際の話が。この fold を繰り返しなソレにしようとしたらば、どうすりゃ良いのか。しかも試験ドリブンなソレでやった方が良いかも。なんとなくヤッツケ感満点だし。

そのナナ

と、言いつつ試験ドリブンは別途とゆー事にして、次の_foldを使って、リストlstに含まれる整数すべての最大公約数を求める手続き(gcd-lst lst)をつくってください(第4回:二をもって一となすより)_を。

gcd は SICP で出てきたんでそれを流用。

(define (gcd-lst lst)
  (define (gcd a b)
    (if (= b 0)
	a
	(gcd b (remainder a b))))
  (define (fold kons knil list)
    (if (null? list)
	knil
	(kons (car list) (fold kons knil (cdr list)))))
  (fold gcd 0 lst))

SICP 曰くの手続き抽象とゆーヤツですな。(しったげ

そのゴ

そのロク

そのナナ

そのハチ