Пролог программы

Question

У меня есть программа:

foo(L,[H|R1]) :-
    foo(L,R1,H).

foo([H],[],H).
foo([H|T],[H|T1],R) :-
    foo(T,T1,R).

Это запрос:

foo([1,2,3,4,5,6],X).

Я не понимаю, что делает эта программа, может кто-нибудь мне помочь и объяснить, как она работает?

Answer 1

Вы можете попытаться изменить его. Если я начну с:

foo(L, [H|R1]) :-
    foo(L, R1, H).

foo([H], [], H).
foo([H|T], [H|T1], R) :-
    foo(T, T1, R).

Я могу изменить порядок аргументов foo (1,2,3) на foo (2,3,1):

foo(L,[H|R1]) :-
    foo(R1, H, L).

foo([], H, [H]).
foo([H|T1], R, [H|T]) :-
    foo(T1, R, T).

Теперь я могу изменить 2-й аргумент foo и передать [H] вместо H:

foo(L, [H|R1]) :-
    foo(R1, [H], L).

foo([], H, H).
foo([H|T1], R, [H|T]) :-
    foo(T1, R, T). 

Теперь вы можете переименовать предикаты для прокрутки и добавления:

roll(L, [H|R1]) :-
    append(R1, [H], L).

append([], H, H).
append([H|T1], R, [H|T]) :-
    append(T1, R, T). 

Answer 2

Чтобы это было проще понять, поместите рекурсивное предложение над базовым:

foo( [H | T], [H | T1], R) :- foo(          /* T = [_|_] */
          T,       T1,  R).
foo( [R],     [],       R).

Таким образом, мы продвигаемся по двум спискам (которые содержат одинаковые элементы, H), пока мы не достигнем последнего элемента в первом списке ([R]), после чего второй список исчерпан ([]) и мы получаем этот последний элемент (R).

Это означает, что foo( A, B, R) :- append( B, [R], A).. Таким образом,

foo( L, [E | R1]) :- % foo( L, R1, E).
                     append( R1, [E], L).    % R1 ++ [E] = L

т.е. foo( L, M) связывает два списка L, M, где L - это M с первым элементом E, «перевернутым» в конец списка:

 L :     .............E
 M :    E.............
 %       ---- R1 -----

Answer 3

В Прологе нет необходимости понимать исходный код. Вместо этого, пусть Prolog сделает это за вас. Просто задайте самый общий запрос :

| ?- foo(L,R).
     L = [_A],
     R = [_A]
  ;  L = [_A,_B],
     R = [_B,_A]
  ;  L = [_A,_B,_C],
     R = [_C,_A,_B]
  ;  L = [_A,_B,_C,_D],
     R = [_D,_A,_B,_C]
  ;  L = [_A,_B,_C,_D,_E],
     R = [_E,_A,_B,_C,_D]
  ;  L = [_A,_B,_C,_D,_E,_F],
     R = [_F,_A,_B,_C,_D,_E]
  ;  L = [_A,_B,_C,_D,_E,_F,_G],
     R = [_G,_A,_B,_C,_D,_E,_F]
  ;  L = [_A,_B,_C,_D,_E,_F,_G,_H],
     R = [_H,_A,_B,_C,_D,_E,_F,_G]
  ;  ...

Вы видите здесь рисунок?