ヲタと呼ばれても仕方がない。

2005-11-15

Uuutokuda2005-11-15

思うのだが 00:39


やっぱり人のコーディングスタイルとかを見るのは勉強になる。

てか、実装はなるべく短く綺麗なほうがよい。

(いっつもオレはクズみたいなコードはいているので、特にそう思う。)


で、そこで皆さんのコードをみてみたいのである。

実際できる人とできないオレの差はそこにもあると思う。

(夏学期はしばしばリスペクトさせてもらったが。)


で、あんまり複雑なのは面倒なので非常に簡単な問題。



二つのツリー(もしくはリスト)が等価であるかどうかを判定するプログラムを示せ。
(深さ優先探索したときの各葉の要素の並びが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であります。


追記:

トラックバックとかしてくれたら見にいきます。

また、オレを捕まえて「ほれほれ、どうじゃ??」と言って下さっても結構です。

班員班員 2005/11/15 21:18 学校に出てきてくだしあ

UuutokudaUuutokuda 2005/11/15 21:20 ごめん、ごめん!!
明日は必ず行きます。

UuutokudaUuutokuda 2005/11/15 21:24 とりあえず、wikiはみました。
また、明日やること指示ください。

kosakkosak 2005/11/15 23:51 解禁記念に書き込みをば(笑)。float の方が遅くても規格には違反しないと思うので、そういう処理系はあり得るかと。でも、それだったら勝手に全部倍精度で演算してくれても良いような気はします(float やら double やらの精度は処理系依存だから、両方同じでも OK)。ちなみに、0.1 とかは文脈によらず double 型の定数なので、リンク先にあるベンチマークでは正しい結果は出ないです。

UuutokudaUuutokuda 2005/11/16 00:28 天上人降臨あげ!!
オレもリンク先のテストはおかしいと思った。
まぁでも、実機ではその辺どうなってるのかちょっと知りたいから、一回試してみてもいいかな。
が、今日はhがブッコしていてゲンナリしているので明日実験してみます。
thanksです☆

namasutenamasute 2005/11/16 13:14 作ってみた。
(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 ’()))

トラックバック - http://d.hatena.ne.jp/Uuutokuda/20051115/1132069191