めざましテレビ

Misc TV

今日の早耳ムスメはみさきゆうさん，お題は「新作を GET！！ 秋のブランドバッグ」．
大人っぽい雰囲気のみさきゆうさん，あまりアップになると大人っぽいを通り越してしまうのがアレなのですが，今日はバッグ特集ということで引き気味のカット中心で一安心．
そうですか，トレンドはチャームですか．
っていうか，チャームって聞くと Cartier とかのアレを想像してしまうのですが，こういうのもチャームと呼ぶんですね．
ってことは，LOUIS VOUITTON のヌメ革パンダもチャームっていうの？
ともあれ (JW)，まさか早耳トレンド No.1 で FENDI のバッグが出てくるとは．
Dior なんかのショップオープンを別とすれば，結構珍しい感じ．


それにしても，二日連続ファッションネタでスタジオに行くとは．
まさかまさか，落差を感じさせないように人選してるんじゃないか？？
そんな余計なこと考えないで，素直に直ちん出してくださいよ．もう待ちきれましぇ〜ん．

Prolog 写経記 その 17 length/2

Tech Prolog

(ほぼ) 毎日淡々と Prolog を写経します．元ネタはこちら．

Prologユーティリティライブラリ

Prologユーティリティライブラリ


昨日写経した last/2 ですが．．．
すでに「その 5」で写経済みでした．(;_;)
ぢぐじょー，完全に忘れてたよ．．． 心より恥じる．
しかも，全然面白くないやつを．．． 無念だ．


次行きますよっ！！ 次，次！！
今日は length/2 を写経します．
これは使ったことはあるけどまだ写経していません．間違いない．

解説

length(List, L) はリスト List の長さを返す．すなわち L を List1 の要素の数に具体化する．

ふむ．Java でいうと List#size() ですね．

モード

length(?, ?)

ふーん．
リストの長さを返すだけじゃなくて，ある長さのリストを返すことも出来る．．． のか？
怪しい．．．

定義

では，こいつの定義を写経しませう．

length([], 0).
length([_|List], L) :-
	length(List, L1),
	L is L1 + 1.

簡単♪

注記

いくつかの Prolog では length/2 は組み込み述語となっている．その組み込み述語は length(+, ?) として実現されており，最後の例に示すような，List が具体化されていない呼び出しは不可能である．

そういえば，これまでに何度か length/2 を使ってきましたが，特に定義しなくても使えましたね．
最後の例が不可能．．． 後でチェックしませう．

例

では使用例を写経しませう．

1 ?- [util].
ERROR: (c:/develop/workspaces/swi/util.swi:86):
        No permission to modify static_procedure `length/2'
ERROR: (c:/develop/workspaces/swi/util.swi:87):
        No permission to modify static_procedure `length/2'

Yes

ぐはぁっ．．．
どうやら組み込み述語は上書きできないようです．．． 無念だ．
しょうがないので length2 に名前を変更しますた．

3 ?- length2([june, july, august], X).

X = 3 

Yes
4 ?- length2(mon, tue, wed, thur, fri, 5).

No
5 ?- length2([[]], Y).

Y = 1 

Yes
6 ?- length2(L, 2), member(x1, L), member(x2, L).

L = [x1, x2] 

Yes

ふーん．
なんか，うまくいっているように見えなくもありませんが．．． ちょっと怪しい．
ちょっと意地悪してみるテスト．

7 ?- length2(L, 2), member(x1, L), member(x2, L).

L = [x1, x2] ;

L = [x2, x1] ;

返ってきません．(^^;
無限ループにいっちゃったっぽいです．ダメじゃん．
やっぱりリストの長さを求めることに専念した方がいいんじゃない？
つまり length(+, ?)．


そんなわけで (どんなわけで？)，組み込み述語の lnegth/2 をお試ししませう．

8 ?- length([june, july, august], X).

X = 3 

Yes
9 ?- length(mon, tue, wed, thur, fri, 5).

No
10 ?- length([[]], Y).

Y = 1 

Yes
11 ?- length(L, 2), member(x1, L), member(x2, L).

L = [x1, x2] ;

L = [x2, x1] ;

No

おぉっ！？
なんか，完璧じゃないですか．ちゃんと length(?, ?) で機能している．．．
やるな SWI-Prolog 組み込み length/2．
でも，不自然な使い方をするのはやめた方が無難な感じ．

差分リスト その 1

Tech Prolog

番外編です♪
Prolog のイディオム．．． なのかなぁ？
まぁ，そんなようなものに差分リストというものがあります．
これはなんだろ？ C でいうところのポインタみたいな存在なのかな？ 分かってる人には普通というか当たり前のものかもしれないけれど，分からない人にはさっぱり，みたいな雰囲気．
その差分リストが写経本以外に教科書として読んでいる「Prolog への入門 (isbn:476490165X)」に，ついに出てきました．わくわく．
が，しかし．．．
説明少なすぎ！！ 2 ページくらいしかないよ？ 原書第三版もあまり違いはない感じ．
そんなに簡単なのか？


たしかに差分リスト自体はとても簡単．
差分リストというのは，リストを二つのリストの差分で表現しようというものです．
たとえば

[a, b, c]

というリストは，次のような差分リストと等価です．

[a, b, c] - []
[a, b, c, d] - [d]
[a, b, c, d, e] - [d, e]

どれも左のリストから右のリスト (の要素) を除くと [a, b, c] になります．
このように，あるリストを表現するのに二つのリストのペアを使うのが差分リスト．
ただし，右のリストは左のリストの末尾と一致しなければなりません．[a, b, c] - [b] みたいなのは差分リストではないということです．


この差分リスト，変数を使うと次のように書くことが出来るそうな．

[a, b, c | Z] - Z

これにより，Z が空リストだろうが [d] だろうが [d, e] だろうが，差分リスト全体としては [a, b, c] を表現することになります．
まぁ，いわれてみれば当たり前な感じ．


差分リスト自体の説明はこんな程度．簡単♪
・・・
なのですが，これだけだと「だからどうした」という気がしないでもありません．
なんで差分リストが必要なの？ 回りくどいだけじゃん？？
と，しばし思っちゃいましたよ．
どうやらですね，差分リストだなんて奇天烈なものがある理由は「効率」のためらしいですぜ，だんな．


例えば N を与えられると，1 から N までの整数を要素とするリストを返す seq/2 という述語を考えてみませう．

2 ?- seq(10, L).

L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

Yes

みたいな．


まずは普通に考えてみます．
1 から N までのリストって事は，1 から N - 1 までのリストの最後に N をくっつければいいって考えるのが Prolog 流な気のせいが．
そんなわけで (どんなわけで？)，

seq1(0, []) :-
	!.
seq1(N, L) :-
	M is N - 1,
	seq1(M, L2),
	conc(L2, [N], L).

という感じになります．最後は conc/3 の代わりにこの前写経した insert_last/3 を使ってもいいのですが，結局は同じなのでこちらで．
これはこれで分かりやすくていいのですが，N が大きくなってくると極端に効率が悪くなります．
というのも，conc/3 は第一引数で渡したリストの要素数分だけ再帰するため，リストの連結は O(N) なんですよね．
なので，N がでかくなってくるととってもいや〜んな気分．
実際，N を 1000 程度にすると目に見えてもっさりと答えを返すようになります．10000 だと 20 秒くらい返ってきません．．．


そこで効率を改善するために，リストの末尾ではなく先頭に要素を追加するように変更します．

seq2(N, L) :-
	seq2(N, 1, L).
seq2(N, N, [N]) :-
	!.
seq2(N, M, [M|L]) :-
	M2 is M + 1,
	seq2(N, M2, L).

下請けの述語 seq2/3 を用意して，N からカウントダウンする代わりに 1 から N までカウントアップしていきます．
この場合，リストの連結は [M|L] なのでそれ自体は O(1) のはず (述語全体での連結の回数は O(N) ですが，それは気にしない気にしない) なので，十分に効率的．N が 10000 でも 100000 でも全然平気，一瞬で返ってきます♪


しかし．
問題によってはこんな風に置き換えるとか出来ない場合もあるかもしれません．
そこで差分リストの登場です．たぶん．
さっそく，seq1/2 を差分リストを使うように書き換えてみます．
こうなりました．じゃーん．

seq3(N, L) :-
	seq3(N, L, []).
seq3(0, Z, Z) :-
	!.
seq3(N, L, Z) :-
	M is N - 1,
	seq3(M, L, [N|Z]).

下請けの述語 seq3/3 を使っていますが，やり方自体は seq1/2 とほとんど同じです．
まず，

seq3(0, Z, Z) :-
	!.

は限りなく

seq1(0, []) :-
	!.

と同じ．なんたって，同じリスト二つの差分 (Z - Z) は空リストに決まっているのだ．
そして

seq3(N, L, Z) :-
	M is N - 1,
	seq3(M, L, [N|Z]).

は限りなく

seq1(N, L) :-
	M is N - 1,
	seq1(M, L2),
	conc(L2, [N], L).

と同じ．ただし，再帰呼び出し後にリストの末尾に要素を追加するのではなく，再帰呼び出し前に差分リストの差分の方の先頭に要素を追加しています．
なぜこれが同等になるのか，差分リストに馴染んでいない頭にはとても奇妙な感じがします．


順を追って考えましょう．例えば

3 ?- seq3(3, L).

なんてやった場合．最終的に [1, 2, 3] というリストを求めたいわけですが，まずは

seq3(N, L) :-
	seq3(N, L, []).

が呼ばれます．この時点 (コンテキスト 1) で具体化されている変数は

  • N = 3

です．
そして seq3/3 を呼び出します．具体的には

	seq3(3, L, []).

です．
呼び出された seq3/3 (コンテキスト 2) では次のように変数が具体化されます．

  • N' = 3
  • Z' = []
  • M' = 2

です．
ここで seq3/3 の再帰呼び出しが行われます．具体的には，

	seq3(2, L, [3|[]]).

となります．
再帰呼び出しされた seq3/3 (コンテキスト 3)では次のように変数が具体化されます．

  • N'' = 2
  • Z'' = [3]
  • M'' = 1

さらに seq3/3 の再帰呼び出しが行われます．具体的には

	seq3(1, L, [2|[3]]).

です．
再帰呼び出しされた seq3/3 (コンテキスト 4) では次のように変数が具体化されます．

  • N''' = 1
  • Z''' = [2, 3]
  • M''' = 0

さらにさらに seq3/3 の再帰呼び出しが行われます．具体的には

	seq3(0, L, [1|[2, 3]]).

です．
ここで第 1 引数が 0 なので，seq3/3 の最初の節が選択されます．

seq3(0, Z, Z) :-
	!.

再帰呼び出しされた seq3/3 (コンテキスト 5) では次のように変数が具体化されます．

  • Z'''' = [1, 2, 3]

ここで最終的に欲しいリストができあがっていることに注意．差分リスト的には [1, 2, 3] - [1, 2, 3] で空リストなんですが．ここポイントですね．
この呼び出しが戻ると，コンテキスト 4 で次の変数が具体化されます．

  • L''' = [1, 2, 3]

このコンテキスト 4 では Z''' = [2, 3] なので，差分リスト的には [1] です．
さらに呼び出しが戻ってコンテキスト 3 で次の変数が具体化されます．

  • L'' = [1, 2, 3]

このコンテキスト 3 では Z'' = [3] なので，差分リスト的には [1, 2] です．
さらに呼び出しが戻ってコンテキスト 2 で次の変数が具体化されます．

  • L' = [1, 2, 3]

このコンテキスト 1 では Z' = [] なので，差分リスト的には [1, 2, 3] です．
そして最後に seq3/2 に呼び出しが戻ってコンテキスト 1 で次の変数が具体化されます．

  • L = [1, 2, 3]

これが求めていた解です．
なんか騙されている感じがしないでもないですが，差分リストを見ると seq1/2 と同じ動きをしていることになります．
なのですが，リストの連結そのものは [N|Z] なので O(1) のはず．
おかげで，N が 10000 でも 100000 でも全然平気，これまた一瞬で返ってきます♪


ようするに，

[X|Z] - Z

という差分リストは，[X] というリストと等価なのだけど，リストを辿ることなく後ろにリストを追加するための変数 Z をあらかじめ仕込んであるのがポイントなのではないかと．たぶん．
と，日記にまとめると簡単に見えるけど，ここまでたどり着くのは結構難儀しました．
差分リストを無意識的に使えるようになるには相当地道に素振りを続けないといけない感じ．Prologer への道は遠いぜ．


差分リストはもっと奥が深いようで，二つの差分リストを連結するというのが主な使い方のようです．
でもでも，差分リスト二つ使うのを考えるのが辛かったので，まずは一つで考えられる方へ逃げてしまいました．心より恥じる．
差分リストの連結についてもそれなりに理解できればまた後日．

アイピ

Misc EbiYuri

日記とアルバムが更新されています．
アルバムには先日放送された「Tokyo美人物語・本当のキレイを探す旅」での写真が追加されました．
キラーナスパでの「思わずポーズ」がいい感じ♪


そして．．．
当面アイピの更新はお休みとのこと．(;_;)
テレビの放送予定とかありがたかったんだけどなぁ．残念．．．
でもでも，友里ちゃんも忙しいようなのでしょうがないですね．


できればオフィシャルサイトの方にスタッフの方が情報を上げてくれるとうれしいんだけどなぁ．．．

CanCam 10 月号 エビちゃんベストセレクション 9

Misc EbiYuri

CanCam2005年10月号の蛯原友里ちゃん

CanCam から，お気に入りの蛯原友里ちゃんを紹介しようというこのコーナー．
今日は Joias とのタイアップ「"輝きのある女"になる！」から P191 の友里ちゃん．
CanCam ではかわいい系担当の友里ちゃんですが，タイアップものではカッコいい系もこなしちゃいます♪
先日の東京ガールズコレクションでデビューした Joias の友里ちゃんはややワイルド＆セクシーなカッコかわいい系？ (^^;
そんなわけで (どんなわけで？)，やっぱり CanCam 買うしか！！