読者です 読者をやめる 読者になる 読者になる

差分リストの練習

取り合えずいくつか無理やり差分リストで書いてみる。

% 深さ優先で左から走査する場合
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]

となるのか。