2005-11-15
■思うのだが
てか、実装はなるべく短く綺麗なほうがよい。
（いっつもオレはクズみたいなコードはいているので、特にそう思う。）
で、そこで皆さんのコードをみてみたいのである。
実際できる人とできないオレの差はそこにもあると思う。
（夏学期はしばしばリスペクトさせてもらったが。）
で、あんまり複雑なのは面倒なので非常に簡単な問題。
二つのツリー（もしくはリスト）が等価であるかどうかを判定するプログラムを示せ。 (深さ優先探索したときの各葉の要素の並びが2つのツリーで等価ってこと)
たとえば、(1 (2 3) (4)) と(1 (2 (3 (4))))は等価である。
言語はなんでもいいですが、
（とかいいつつ関数型言語リングつくっちゃったから、できれば関数型で）
短くて綺麗でかつ計算量の小さいソースをお願いします。
Schemeを書きたいpla☆くんや暇な人はどうぞ。
んで、オレのソースは↓（結構長いんですよ、やっぱり）
(define (equal? lst1 lst2)
(letrec ((flatten
(lambda (tree)
(if (null? tree)
(list)
(if (pair? (car tree))
(flatten (append (car tree) (cdr tree)))
(cons (car tree) (flatten (cdr tree)))))))
(compare-list
(lambda (list1 list2)
(if (and (null? list1) (null? list2))
#t
(if (or (null? list1) (null? list2))
#f
(and (eq? (car list1) (car list2)) (compare-list (cdr list1) (cdr list2))))))))
(compare-list (flatten lst1) (flatten lst2))))
word数は62であります。
追記：
トラックバックとかしてくれたら見にいきます。
また、オレを捕まえて「ほれほれ、どうじゃ??」と言って下さっても結構です。
トラックバック - http://d.hatena.ne.jp/Uuutokuda/20051115/1132069191
リンク元
- 64 http://is.zng.info/antenna/
- 19 http://practical-scheme.net/wiliki/wiliki.cgi?Shiro
- 12 http://www.shiro.dreamhost.com/scheme/wiliki/wiliki.cgi?Shiro
- 5 http://d.hatena.ne.jp/succeed/
- 5 http://d.hatena.ne.jp/succeed/20051115
- 4 http://a.hatena.ne.jp/succeed/
- 4 http://gesuyabao.ring.hatena.ne.jp/
- 3 http://d.hatena.ne.jp/okeihan0831/
- 3 http://functions.ring.hatena.ne.jp/
- 3 http://mixi.jp/home.pl
明日は必ず行きます。
また、明日やること指示ください。
オレもリンク先のテストはおかしいと思った。
まぁでも、実機ではその辺どうなってるのかちょっと知りたいから、一回試してみてもいいかな。
が、今日はhがブッコしていてゲンナリしているので明日実験してみます。
thanksです☆
(define (equal? lst1 lst2)
(define (f l1 r1)
(define (g l2 r2)
(cond
((pair? l2) (g (car l2) (cons (cdr l2) r2)))
((null? l2) (if (null? r2) (null? l1) (g (car r2) (cdr r2))))
(else (and (eq? l1 l2) (equal? r1 r2)))))
(cond
((pair? l1) (f (car l1) (cons (cdr l1) r1)))
((and (null? l1) (pair? r1)) (f (car r1) (cdr r1)))
(else (g lst2 ’()))))
(f lst1 ’()))