Hatena::Groupsicp

SICP読書記

|

2009-11-19

問題2.54

問題2.54 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.54 - SICP読書記

図形言語は豪快にスキップ

(define (equal? x y)
  (if (and (pair? x) (pair? y))
	  (if (equal? (car x) (car y))
		  (equal? (cdr x) (cdr y))
		  #f)
	  (eq? x y)))

;; #t
(equal? '(this is a list) '(this is a list))

;;#f
(equal? '(this is a list) '(this (is a) list))

carがequalならcdrがequalかどうかを返せばよいという戦略。

carがequalでなければequalではない。

2ついずれかが対でなければそれらの要素のeqを返せばよい。

問題2.59

問題2.59 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.59 - SICP読書記

記号微分もあっさりスキップ。

(define (union-set set1 set2)
  (fold (lambda (x resultset)
		  (if (element-of-set? x resultset)
			  resultset
			  (cons x resultset)))
		'()
		(append set1 set2)))


(print (union-set '(a b c) '(a c e)))

set1とset2の要素をfoldでたたみ込む。

すでにリストに含まれている要素は足さない。

実行結果は

 (e c b a)

こんなのもあるかな。

(define (union-set set1 set2)
  (append (filter (lambda (e) (not (element-of-set? e set2)))
				  set1)
		  set2))

set1の要素でset2に含まれないものとset2の要素を足したもの。

問題2.60

問題2.60 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.60 - SICP読書記

(define (element-of-set? x set)
  (cond ((null? set) #f)
		((equal? x (car set)) #t)
		(else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (cons x set))


(define (intersection-set set1 set2)
  (filter (lambda (e)  (and (element-of-set? e set1)
		(element-of-set? e set2)))
	(append set1 set2)))

(define (union-set set1 set2)
  (append set1 set2))

element-of-setは変更なし。

adjoin-setは重複していいので、何も考えずcons

intersection-setは、二つのリストを足して、両方に含まれる要素だけをたたみ込む

union-setは何も考えずappendでOK

2009-11-14

問題2.43

 問題2.43 - SICP読書記 を含むブックマーク はてなブックマーク -  問題2.43 - SICP読書記

(define (queen board-size)
  (define (queen-cols k)
	(if (= k 0)
		(list empty-board)
		;; 解答の中からリストの中から安全なものをフィルタ
		(filter 
		 (lambda (positions) (safe? k positions))
		 ;; k行目に置いた場合の全てのパターンのリストを返す
		 ;; k行目に置いたものはpositionsの最初にある
		 (flatmap
		  (lambda (rest-of-queens)
			;; new-row : k列目にクイーンをおける行の案
			(map (lambda (new-row)
				   (adjoin-position new-row k rest-of-queens))
				 (enumerate-interval 1 board-size)))
		  (queen-cols (- k 1))))))
  (queen-cols board-size))

(define empty-board ())

(define (adjoin-position row col queens)
  (cons (list row col) queens))

(define (safe? new-col ps)
  (let ((new-row (caar ps))
		(rest (cdr ps)))
  (define (safe-simple? p)
	(let ((old-row (car p))
		  (old-col (cadr p)))
	  (and
	   ;; 同じ行でないこと
	   (not (= new-row old-row))
	   ;; 右上から左下の斜め方向で当たらないこと
	   (not (= (+ new-row new-col)
			   (+ old-row old-col)))
	   ;; 左上から右下の斜め方向で当たらないこと
	   (not (= (- new-row new-col)
			   (- old-row old-col))))))
  (all? safe-simple? rest)))
  

(print (queen 4))

all?は以下

(define (all? f ls)
  (cond ((null? ls) #t)
		((not (f (car ls))) #f)
		(else (all? f (cdr ls)))))
(18003)> gosh p72-2.42.scm 
(((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))

おそらく合っていると思う。

でもこの問題の前提になっているp73のプログラムって、あんまりきれいじゃないような。。。safe?に渡すpositionsに、すでに新しいクイーンが置かれていて、リストの最初のクイーンが新しいものだとかいう前提があるプログラム。うーむ。

問題2.43

問題2.43 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.43 - SICP読書記

(flatmap
 (lambda (new-row)
  (map (lambda (rest-of-queens)
         (adjoin-position new-row k rest-of-queens))
       (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))

こうした場合になぜ遅くなるか、という問題。

queen-colsの実行される回数がまるで違うと直感。

例えばboard-size=8で、最後の8col目のクイーンを置く位置を計算するタイミングにおいて、

元に比べてどのぐらい掛かるかって式で表すのは。。。やめとこう。

2009-11-06

問題2.23 評価式の結果を表示してしまう問題

| 問題2.23 評価式の結果を表示してしまう問題 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.23 評価式の結果を表示してしまう問題 - SICP読書記

http://sicp.g.hatena.ne.jp/Hayato/20080806/p5

sicp-lite #6で話題になった件。

最後、#undefとか#tとか()とかが表示されちゃう。

それは対話型で実行しているため、入力した式の結果が表示される。

上記リンク先のようにmainをdefineして、"gosh hoge.scm"のように実行すれば、数字だけが表示される。

ところで、自分はgosh hoge.scmを実行したら復帰値が70になったんだけどそれはなんでなんだろう。

$ gosh hoge.scm
57
321
88

$ echo $?
70

2009-10-18

問題2.32

|  問題2.32 - SICP読書記 を含むブックマーク はてなブックマーク -  問題2.32 - SICP読書記

次回SICP Liteでは、弱者に問題2.32を教えてください(他力本願なり〜)。このコードがどう動くか、また、どうやったらこんなコードが思い浮かぶか。。。普通に命令型で書くとどうなるか、てのもおもろいかも。 #sicplite

Twitter / Tomokatsu Mizukusa: 次回SICP Liteでは、弱者に問題2.32を教え ...

ってかいてあったけど、自分は見事に飛ばしていたので再度やってみた。

(use slib)
(require 'trace)
(define debug:max-count 20)

(define (subsets s)
  (define (f arg)
	(cons (car s) arg))
  (if (null? s)
	  (list '())
	  (let ((rest (subsets (cdr s))))
		(append rest (map f rest)))))

(trace subsets)

(print (subsets (list 1 2 3)))

結果

CALL subsets (1 2 3)
 CALL subsets (2 3)
  CALL subsets (3)
   CALL subsets ()
   RETN subsets (())
  RETN subsets (() (3))
 RETN subsets (() (3) (2) (2 3))
RETN subsets (() (...) (...) (...) (1) (1 ...) (1 2) (1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
#t

トレースを見るとなんとなく動く理由はわかった。

全ての部分集合の集合とは、その集合からある要素eをのぞいた集合の全ての部分集合Aと、Aの全ての要素にeを加えたものであるから。

ううん、、、コードを日本語に訳しただけですね。しかも明快でもないような。


あと、どうやったらこんなコードが思い浮かぶかというのもよく分かりません。たぶん、ここを読んだ時点で思い浮かばないから穴埋め問題にはなってるんだろうけど。。。

2009-09-09

再帰の柔軟性

再帰の柔軟性 - SICP読書記 を含むブックマーク はてなブックマーク - 再帰の柔軟性 - SICP読書記

つまり、プログラマがループを意識して再帰を書かなきゃいけない時点で負けのような気がする。ループより先に末尾再帰の形が思いつく、っていう脳を持ってる人はこれでもいいのかもしれないけど。再帰が美しいんだ!!!とかいう話にはあんまり興味はないし、新しいことができるわけじゃないし、何かが良くなる気もしない。

問題1.11と末尾再帰への変換 - SICP読書記 - sicp

こんなことを思っている人は、


Schemeプログラマ再帰を好んで使う理由は、こんな柔軟性なんだ。

なんでも再帰

上の「開かれたループ」の部分まで読むといいよ。

なるほど、再帰関数によって構成されていることと高階関数を組み合わせると、楽しい場面はたしかにある。

|