[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part4 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
477(4): 2006/04/17(月)22:14 AAS
木を使うアルゴリズムなんてほとんど知らないんだが…
いちおうこんなのを考えてみた。
data Bound a = Inclusive a | Exclusive a | Unbounded -- 範囲の境界
type Range a = (Bound a, Bound a) -- (下限、上限)
data RangeMap k a =... -- kの範囲にaの値を対応させる写像。木で表現される。平衡木だとなおよい。
empty :: (Ord k) => RangeMap k a -- 空の写像
insert :: (Ord k) => Range k -> RangeMap k a -> RangeMap k a --既存の写像を部分的に上書き
省5
480: 2006/04/17(月)22:43 AAS
>>479
>>477
489: 2006/04/18(火)00:29 AAS
>>477
ツォルンの補題まで行ってきました。
なんでそうなったかは自分でもよくわかりません。
明日のナゾナゾにしてもう寝ます。
495(1): 2006/04/18(火)17:07 AAS
>>477
a<b<c<d のとき(a,c)<(b,d)ということでしょうか？
でも(a,d)と(b,c)の比較がやっぱり分りません。(a,d)>(b,c)なんだろうか・・・
RangeMapはこういう解釈でいいんでしょうか？
・RangeMap型のオブジェクトは次の写像と同値である。
r(1),r(2)...r(n)のn個の整列された範囲が与えられているとき、
範囲rを自然数iに対応させる写像であって、rをr(i)とr(i+1)との間に挿入すると
省2
496: 2006/04/18(火)20:13 AAS
>>495
説明不足だった。申し訳ない。
意図としては、RangeMapはk型の値からa型の値への写像。
例えば、
a0, a1 :: RangeMap Integer String
a0 = insert (Unbounded, Unbounded) "foo" empty
a1 = insert (Inclusive 0, Inclusive 10) "bar" a0
省3
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.145s*