Я выяснил код для проверки равных a и b в списке, но не могу понять базовую рекурсию

Question

s(A,A).
s(A,D):- l(A,B),s(B,C),r(C,D).

l([a|A],A).

r([b|A],A).

Приведенный выше код в прологе проверяет, имеют ли заданные входные данные списка равные a и b или нет.

Например,

s([a,a,b,b],[]).
True.

Это включает в себя списки рекурсии и различий,Может кто-нибудь объяснить, как лежащие в основе проверки рекурсии равны a и b шаг за шагом.

Answer 1

s(  A, A).               % s(0).
s(  A,       D) :-       % s(n):-
  l(A, B),               %   before,
     s(B, C),            %   s(n-1),
  r(      C, D).         %   after.

l(  [a | A], 
         A ).
r(  [b | B], 
         B ).

вместе определяют

%% 1 
s(          [a , b | B1], B1):-
          l([a | A1],
                 A1 ),
              s( A1,      %s0%
                 A1 ),    %s0%
          r(    [b | B1],
                          B1 ).

и

%% 2 
s(      [a , a , b , b | B2], B2):-
      l([a | A2],
             A2 ),
          l([a | A1],              %s1%
                 A1 ),             %s1%
              s( A1,      %s0%     %s1%
                 A1 ),    %s0%     %s1%
          r(    [b | B1],          %s1%
                     B1 ),         %s1%
      r(            [b | B2],
                              B2 ).

и

%% 3 
s(  [a , a , a , b , b , b | B3], B3):-
  l([a | A3],
         A3 ),
      l([a | A2],                            %s2%
             A2 ),                           %s2%
          l([a | A1],              %s1%      %s2%
                 A1 ),             %s1%      %s2%
              s( A1,      %s0%     %s1%      %s2%
                 A1 ),    %s0%     %s1%      %s2%
          r(    [b | B1],          %s1%      %s2%
                     B1 ),         %s1%      %s2%
      r(            [b | B2],                %s2%
                         B2 ),               %s2%
  r(                    [b | B3],
                                  B3 ).

и т. Д. И т. П.

Answer 2

Различия в списке нелегко понять, если рассуждать о них на низком уровне.

Поэтому я сначала рекомендую более высокоуровневое представление:

В целом, ваш предикат s/2 описывает список .Я говорю «описывает», потому что он не только «проверяет», но и генерирует и завершает такие списки, если мы хотим!

Мы можем прочитать каждую цель s/2 как «и затем некоторый элемент (элементы) списка».

Итак, на минуту забудем об аргументах и ​​рассмотрим абстрактную структуру сказуемое.Я использую (-->)/2 сейчас вместо (:-)/2, чтобы прояснить, что я говорю о небольшом варианте предиката, где я просто игнорирую аргументы:

s --> [].
s --> l, s, r.

Мы можем сделать то же самое с l/2 и r/2:

l --> [a].
r --> [b].

Это то, что предикаты описывают в абстрактном представлении списков high-level .В этой записи мне не нужно бороться со списком различий и аргументов.Вместо этого я могу сосредоточиться непосредственно на сущности программы.

Очевидно, что вы можете легко перевести такой высокоуровневый код в код, который вы разместили.Фактически, Prolog выполняет этот перевод для вас, если вы обращаетесь к этому коду: он называется DCG нотация .См. dcg для получения дополнительной информации.

Итак, теперь все ясно: s//0 описывает список, который либо пуст , либо:

• список, описанный l//0
• , а затем список, описанный s//0
• , а затем список, описанный r//0.

Поскольку l//0 описывает список с одним элементом a, а r//0 описывает список с одним элементом b, ясно, что в спискахs//0 описывает, всегда есть одно и то же число a с и b с.

Мы используем phrase/2 для вызова DCG.Например:

<b>?- phrase(s, Ls).</b>
Ls = [] ;
Ls = [a, b] ;
Ls = [a, a, b, b] ;
Ls = [a, a, a, b, b, b] .

Если вы начнете явно рассуждать о рекурсии, вы не добьетесь большого прогресса, потому что быстро становится слишком сложно отследить точные шаги, которые выполняет движок Prolog, и выполнитьвсе возможности во внимание.Я рекомендую вам сосредоточиться на значении ваших предикатов и попытаться понять, что они на самом деле описывают.

РЕДАКТИРОВАТЬ : Если вы хотите явно аргументировать аргументы, может помочь алгебраическая аналогия: Мы можем рассматривать каждую пару аргументов как описание списка как " разница " между двумя списками, разница списка , также по аналогии с дифференциал Δ используется в исчислении.

Например, «разница» между [X,Y,Z|Rs] и Rs равна [X,Y,Z].Следовательно, по крайней мере, символически мы можем написать:

Обозначим через L, L ₀ , L ₁ и L ₂ списки, которые описываются такими различиями во втором пункте:

Алгебраически мыможно рассматривать L как " sum " (объединение) других списков:

Для остальных списков мыиметь:

Итак, в итоге имеем:

Обратите внимание, что для понимания этого не требуется рекурсия.Вместо этого важнее всего отношение между аргументами.Лично я также нахожу такой вывод менее полезным, чем обратное: я думаю, что гораздо важнее заметить этот паттерн при написании такого кода, потому что это означает, что вы можете использовать нотацию DCG вместо , и значительноуменьшите количество передаваемых аргументов!