FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

01.26
Sat
集合で{a,b}{b,a}は等しいものですが、順番も考慮したい時があります。

ならびも考慮したやつを順序対と言うのですがこれがどうやらデータ構造を表すのに使えるっぽい

対って基本的に2つの元をとって

それを入れ子にすることでデータのならびを表すみたいです

それってLispのドット対にそっくりですよね

(a . (b . (c . (d . (e . nil))))) == (a b c d e)

リストってドット対で書けるんで

で、その順序対ってのを非順序対で表すと

(x , y) := {{x} , {x , y}}となるらしいです

これにはいくつか定義があって

上はクラトフスキーの定義らしいです

これがメジャーだとか

クラトフスキーの定義

で、和集合とか積集合とか差集合で要素が取り出せるみたいです

なのでそれをSchemeでかんーたんな感じにやってみる


(define-macro (iflet var result proc then els)
	`(let ((,var ,result))
		(if (,proc ,var) ,then ,els)))

(define-macro (ifzero n then els)
	`(if (= ,n 0) ,then ,els))

(define-macro (ifnil lst then els)
	`(if (null? ,lst) ,then ,els))


(define nil ())

(define (filter proc lst)
	(ifnil lst
		nil
		(iflet factor (car lst) proc
			(cons factor (filter proc (cdr lst)))
			(filter proc (cdr lst)))))

(define (one? lst)(= (length lst) 1))



(define (union set1 set2)
	(ifnil set1
		set2
		(if (not (member (car set1) set2))
			(union (cdr set1) (cons (car set1) set2))
			(union (cdr set1) set2))))

(define (p-union set)
	(if (one? set)
		(car set)
		(union (car set) (p-union (cdr set)))))

(define (inter set1 set2)
	(ifnil set1
		set1
		(if (member (car set1) set2)
			(cons (car set1) (inter (cdr set1) set2))
			(inter (cdr set1) set2))))

(define (p-inter set)
	(if (one? set)
		(car set)
		(inter (car set) (p-inter (cdr set)))))

(define (differ set1 set2 :optional (pred? eq?))
	(ifnil set1
		set2
		(differ (cdr set1) (filter (^ (elm) (not (pred? elm (car set1)))) set2))))



(define op-d '((x) (x y)) ) 
(define op-t '((x) (x ((y) (y z)))))
(define op-q '((w) (w ((x) (x ((y) (y z)))))))

;<x,y>     := {{x} , {x,y}}
;<x,y,z>   := {{x} , {x , {{y} ,{y,z}}}}
;<w,x,y,z> := {{w} , {w , {{x} , {x {{y} , {y , z}}}}}}

(define (fst double) (p-union (p-inter double)))
(define (snd double)
	;;シングルトンの時にうまくいかなくなるので
	(if (equal? (p-inter double) (p-union double))
		(fst double)
		(p-inter (differ (p-inter double) (p-union double)))))



(define (main argv)
	;;<w,x,y,z>のyをとる	
	(print (fst (snd (snd op-q)))))
スポンサーサイト

comment 1 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/162-2bbbb533
トラックバック
コメント
「裏技フリーソフトの秘密基地」を運営しているアイスマンと申します。
突然で申し訳御座いませんが、貴方様のサイトと相互リンクしていただけませんでしょうか?

サイトタイトル : 「裏技フリーソフトの秘密基地」

サイトURL : http://kokoichi6063.blog.fc2.com/

サイト内容 : パソコンで使えるフリーソフトの紹介や、便利サイトの利用方法などを細かく解説しているサイトです。
最近は、IT経済ニュースなどの記事も書いております。

お願い : 現時点で貴方様のサイトのリンクは、はってありますが3日以内に返事がいただけない場合は一時的にリンクをはずさせてもらいます。

よろしければ相互リンクお願いします。
長々とすいませんでした。
アイスマン | 2013.01.31 19:16 | 編集
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。