Prolog 写経記 その 14 insert_n/4
(ほぼ) 毎日淡々と Prolog を写経します．元ネタはこちら．
- 作者: ボグダンフィリピッチ,中島誠,伊藤哲郎
- 出版社/メーカー: 海文堂出版
- 発売日: 1990/08
- メディア: 単行本
- 購入: 4人 クリック: 33回
- この商品を含むブログ (68件) を見る
insert_n/4 を写経します．解説
insert_n(N, X, List1, List2)は要素XをList1のN番目の位置に挿入した新しいリストをList2として返す．
ふむ．Java でいうと List#add(int, Object) みたいな．
モード
insert_n(?, ?, ?, ?)
ふむ．まぁ例によって．
定義
では，こいつの定義を写経しませう．
insert_n(N, X, List1, List2) :- conc(L1, L2, List1), length(L1, L), N is L + 1, conc(L1, [X|L2], List2).
基本的な発想はいつも通りですね．
リストを X とその左の要素からなるリスト (L1)，右の要素からなるリスト (L2) に分けて，
L1とL2を連結したリストがList1．L1，X，L2を連結したリストがList2．
ということですね．
その上で，L1 の長さは N - 1 ってことを示すのが
length(L1, L), N is L + 1,
の部分．
こういうのはやっぱりこうなるんですね．ってことなら，フィジカルネタでおいらがやったこともそんなに手続き的というわけでもないのだろうか？
注記
以下の例は
insert_nがそれぞれ初期設定された引数の違いによってどのように適用できるかを示している．バックトラック時に無限ループに陥るのを避けるため，List1は少なくとも部分的に具体化されている必要がある．
例によって無限ループの危険性がある，と．らじゃあ．
例
では使用例を写経しませう．
2 ?- insert_n(3, 4/5, [1/2, 2/3, 4/4], L). L = [1/2, 2/3, 4/5, 4/4] ; No 3 ?- insert_n(N, b, [_, _, _], [a, b, c, d]). N = 2 ; No 4 ?- insert_n(P, X, [4, 6], [2, 4, 6]). P = 1 X = 2 ; No
2 番目の例が List1 を「部分的に具体化」した例ですね．
これを全く具体化せずに呼び出してみると．．．
5 ?- insert_n(N, b, L, [a, b, c, d]). N = 2 L = [a, c, d] ;
．．．
別の解を求めるためのセミコロンを入力した後，きっちり無限ループになって返ってきません．(^^;
部分的に具体化
「フィジカルを鍛える練習問題：二分探索木」で作ったプログラムを「部分的に具体化」を使うように修正してみました．
一番肝心な (？) add_value/3 はこんな感じになりました．
add_value(Value, Node, node(Value, _, _)) :- var(Node). add_value(Value, Node, Node) :- get_value(Node, Value). add_value(Value1, Node, Node) :- get_value(Node, Value2), Value1 < Value2, get_left(Node, Left), add_value(Value1, Left, Left). add_value(Value1, Node, Node) :- get_value(Node, Value2), Value1 > Value2, get_right(Node, Right), add_value(Value1, Right, Right).
最初の節以外は第 2 引数と第 3 引数が同じ．なので，ツリーのコピーは行われていないはず．
ちなみに旧版はこんな感じでした．
add_value(Value, nil, node(Value, nil, nil)). add_value(Value, Node, Node) :- get_value(Node, Value). add_value(Value1, node(Value2, Left, Right), node(Value2, Left2, Right)) :- Value1 < Value2, add_value(Value1, Left, Left2). add_value(Value1, node(Value2, Left, Right), node(Value2, Left, Right2)) :- Value1 > Value2, add_value(Value1, Right, Right2).
大きく違うのは 3 番目の節と 4 番目の節．ツリーに新しいノードを追加する場合，こちらは再帰的に新しいノードを作成しています．
この旧版だと例えば．．．
2 ?- add_value(3, _, N1), add_value(2, N1, N2), add_value(1, N2, N3), add_value(4, N3, N4), add_value(5, N4, N5). N1 = node(3, nil, nil) N2 = node(3, node(2, nil, nil), nil) N3 = node(3, node(2, node(1, nil, nil), nil), nil) N4 = node(3, node(2, node(1, nil, nil), nil), node(4, nil, nil)) N5 = node(3, node(2, node(1, nil, nil), nil), node(4, nil, node(5, nil, nil))) Yes
というように，ツリーに要素を追加するたびに新たなツリーを作成している様子が窺えます．
一方新版だと，
5 ?- add_value(3, _, N1), add_value(2, N1, N2), add_value(1, N2, N3), add_value(4, N3, N4), add_value(5, N4, N5). N1 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043))) N2 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043))) N3 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043))) N4 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043))) N5 = node(3, node(2, node(1, _G1034, _G1035), _G1031), node(4, _G1038, node(5, _G1042, _G1043))) Yes
と，最終的には全てのツリーが同じになっています．ツリーに要素を追加しても新たなツリーが作成されていないということが分かります．
やったね！！
でもでも，ツリーから要素を削除する場合をどうすればいいかが分からない．．．
一度具体化した変数をもう一度具体化されていない変数に戻すなんてあり得ないような気のせいが．
ってことは，削除の場合はツリーのコピーを作るしかないのだろうか？ うーみゅ．．．
Prolog 本発送
未発送だった書籍が 2冊ばかり発送された模様．
一つはこちら．
ICSS.Bratko: Prolog Programming f_p3 (3rd Edition) (International Computer Science Series)
- 作者: Ivan Bratko
- 出版社/メーカー: Pearson
- 発売日: 2000/09/18
- メディア: ペーパーバック
- クリック: 2回
- この商品を含むブログ (4件) を見る
でもでも，まだ前半である「Prolog への入門 (isbn:476490165X)」も読み終えてないのですが．．． 心より恥じる．
もう一冊はこちら．
- 作者: Max Bramer
- 出版社/メーカー: Springer
- 発売日: 2005/07/01
- メディア: ペーパーバック
- クリック: 5回
- この商品を含むブログ (3件) を見る
(^^;まだしばらく届かないと思っていたので予定外．困るなぁ．
ちなみにこの2冊，少し前に注文した後値下がりしたので昨日キャンセルして改めて注文し直したばかり．せこい？ (^^;
前者の価格差は数十円だったので普通ならそんなことしないのですが，後者は 6,400 円から 5,645 円へと大きく値下がりしたのでちょっともったいないな，と思った次第．
注文してから発送まで時間がかかるやつは注意しないと結構値段が変わるんですよね．
当然ですが，値上がりした場合はそのままです．(^^;
Inter 3 - 0 Treviso
＼(^o^)／ ＼(^o^)／ ＼(^o^)／ ＼(^o^)／ ＼(^o^)／
開幕戦を圧勝！！
し・か・も
Adriano がいきなりの Tripletta！！！！
いける．今年こそはいける．間違いない．
今日，期待は確信に変わった．
そ・し・て
お隣はドロースタート♪
まるで昨年のこっちを見ているようだ (苦笑)．
