Процедура размера на языке Пролог

Question

Я новичок в Прологе и не настолько хорош, когда речь заходит о рекурсивных алгоритмах, как есть, поэтому меня смущают следующие два предложения:

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

У меня проблемы с отслеживанием этой проблемы:

?- size([a,b,c,d], N).

Это объединится со вторым предложением, чтобы сформировать:

size([a,b,c,d], N) :- size([b,c,d], N1), N is N1+1.

Но меня смущает N является N1+1 поскольку эти переменные никогда не объединяются. Какие значения принимают эти переменные?

Любая помощь по этому вопросу, или простой след этого алгоритма, будет принята с благодарностью.

Answer 1

N равно N1+1, поскольку эти переменные никогда не объединяются.

Я думаю, вы имеете в виду, что они никогда не создаются, то есть никогда не получают значения. Объединение двух переменных может создавать их экземпляры, но это не обязательно. Например, вы можете запустить это в прологе REPL:

?- N = N1.
N = N1.

в то время как N а также N1 не имеют значения (пока), они едины; если N1 будет создан позже, N будет создан с тем же значением. Еще один, менее тривиальный пример:

?- [H|T] = L, L = [1|M], writeln(H).
1
H = 1,
T = M,
L = [1|M].

Тем не менее, это правда, что N никогда не объединяется с N1+1! is будет оценивать N1+1 и это значение будет объединено с N, Это произойдет после внутреннего size([b,c,d],N1) был оценен так N1 переменная будет создана.

По сути, выполнение будет так:

size([a,b,c,d],N).
          size([b,c,d],N1)
               size([c,d],N1)
                   size([d],N1)
                        size([],0)
                        N is 0+1.
                   N is 1+1.
               N is 2+1.
          N is 3+1.

Что немного неэффективно, так как нам нужно хранить все вызовы функций в памяти; посмотрите на хвостовую рекурсию и аккумуляторы, чтобы это исправить.

Также обратите внимание, что N1 нужно создавать только потому, что is собирается оценить выражение. Вы могли бы написать что-то вроде этого:

size([],0).
size([_|T], 1+ N1):-size(T,N1).

и если вы называете это:

?- size([1,2],N).
N = 0+1+1.

Веселье, не правда ли? Вы можете оценить последний N, например, назвать его как size([1,2],N), Result is N, Тем не менее, одна проблема заключается в том, что мы держим цепочку 0+1+1+1+1+...... в памяти, которая может стать большой очень быстро. Так что лучше всего использовать этот трюк для вещей, которые не будут расти, например, шаблонов выражений.