非決定性の述語単位行列/2

Prolog

【出典】https://twitter.com/TakaoOzaki/status/306175708726706177
【要約】述語単位行列/2 を“うまく”定義する。

単位行列 E_n := [ δ_i,j ]_n×n からの連想として「添字」を用いる実装をすると、双方向性を保つのがめんどくさい
(組み込み述語 var による条件分岐がどうしても必要になる気がする)。

【出典】https://twitter.com/TakaoOzaki/status/306175708726706177
【要約】述語単位行列/2 を“うまく”定義する。

ue_dai
2013/2/26 11:19

タグ：
タグはありません

mylength([], 0).
mylength([_|T], N) :- mylength(T, N1), N is N1 + 1.

零リスト([]).
零リスト([0|T]) :- 零リスト(T).

単位行列(N, LL) :- mylength(LL, N), 単位行列_(N, LL).
単位行列_(0, []).
単位行列_(N, [[1|RowT]|T]) :-
%	number(N), N > 0,
	N1 is N - 1, mylength(RowT, N1), !,	% important!
	行列の左に列ベクトルを加える(T1, ClmT, T),
	零リスト(RowT), 零リスト(ClmT),
	単位行列_(N1, T1).

行列の左に列ベクトルを加える([], [], []).
行列の左に列ベクトルを加える([T|LL1], [H|V], [[H|T]|LL]) :-
	行列の左に列ベクトルを加える(LL1, V, LL).

?- 単位行列(2, [[1, 0], [0, 1]]).
/*
yes
*/

?- 単位行列(N, [[1, 0], [0, 1]]).
/*
N = 2 ;
no
*/

% うまく定義しないと no が返らず無限ループに陥ることも。

?- 単位行列(2, LL).
/*
LL = [[1, 0], [0, 1]] ;
... (無限ループに陥る)
*/

% no を返してほしいところだが、次の結果を得るためにはこの挙動にならざるをえない？

?- 単位行列(N, LL).
/*
N = 0, LL = [] ;
N = 1, LL = [[1, 0], [0, 1]] ;
N = 2, LL = [[1, 0, 0], [0, 1, 0], [0, 0, 1]] ;
N = 3, LL = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]] ;
... (各Nについて無限に成功する)
*/

% うまく定義しないと N = 0, 1 だけで終わってしまうことも。

このコードをツイートする

非決定性の述語 単位行列/2

非決定性の述語単位行列/2