差分リストの練習
取り合えずいくつか無理やり差分リストで書いてみる。
% 深さ優先で左から走査する場合 flatten(NestedList, FlatList) :- flatten_sub(NestedList, [FlatList, []]). flatten_sub([X | Xs], [Head , Tail]) :- flatten_sub(X, [Head, Appender]), flatten_sub(Xs, [Appender, Tail]), !. flatten_sub(X, [[X | Head], Head]) :- X \== []. flatten_sub(_, [Tail, Tail]). % リストの先頭の要素から走査する場合 my_append(X, Y, R) :- append_sub(X, [R, Y]). append_sub([X | Xs], [Rs, Y]) :- [Rs, Rs1] = [[X | Rs1], Rs2], append_sub(Xs, [Rs2, Y]), !. append_sub(_, [Y, Y]). % リストの間にitemを入れる。単純走査の発展系 intersperse(List, Item, Result) :- intersperse_sub(List, Item, [[_ |Result], []]). intersperse_sub([X | Xs], Item, [Result, Tail]) :- [Result, Appender1] = [[Item, X | Appender1], Appender2], intersperse_sub(Xs, Item, [Appender2, Tail]), !. intersperse_sub(_, _, [Tail, Tail]).
実行結果
| ?- flatten([a,b,c,[d,e,f],g,[h, i, [j,k], l], m], R). flatten([a,b,c,[d,e,f],g,[h, i, [j,k], l], m], R). R = [a,b,c,d,e,f,g,h,i,j,k,l,m] yes | ?- my_append([a,b,[c,d],e,[f,g], h], [i,j], R). my_append([a,b,[c,d],e,[f,g], h], [i,j], R). R = [a,b,[c,d],e,[f,g],h,i,j] yes | ?- my_append([], [i,j], R). my_append([], [i,j], R). R = [i,j] yes | ?- my_append([], [], R). my_append([], [], R). R = [] yes | ?- intersperse([a,b,c,d,e,f,g], 1, R). intersperse([a,b,c,d,e,f,g], 1, R). R = [a,1,b,1,c,1,d,1,e,1,f,1,g] yes | ?-
図示
intersperse([a,b], 1, R).
を考えるとき、
Result Appender1 <-- Appender2 | | | | | | v v 1, a, ?
となり、次の時は
Result (Result) (Appender1)<-- (Appender2) | | | | Appender1 <-- Appender2 | | | v v v 1, a, 1, b, ?
最後は
(Result) (Result) (Appender1)<-- (Appender2) | | | | (Appender1)<-- (Appender2) <-- [] | | | v v v 1, a, 1, b, []
となって、最終的に、
Result(途中) | | | v 1, a, 1, b, [] Result(途中) = [1, a, 1, b] = [_ | Result] Result = [a, 1, b]
となるのか。