Поиск подсписка, соответствующего определенным критериям, с помощью программы на Прологе с хвостовой рекурсией

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

e.g.

?- longest_asc_sublist([1,2,3,2,8,4,7,8,10,11,7,-1],From,To).
From = 6,
To = 10.

Что у меня есть до сих пор и в чем моя проблема: в основном я пытался реализовать алгоритм с помощью его псевдокода, который делал бы именно то, что мне нужно, но моя проблема в том, что я не могу понять, как сделать это работает с операторами if, без следующего за ними «else», которые имеют несколько действий в своем заявлении или делают это без if

longest_asc_sublist(List,_,_) :- longest_asc_sublist(List,1,1,1,0,1,1).
longest_asc_sublist([],V,K,K,_,V,_).
longest_asc_sublist([X,Xs|Xss],_,_,K,T,V,M) :-

                            K1 is K+1, T1 is T+1,

                            Xs < X, !,           % this would be an if condition
                            T1 is 1, V1 is K,    % and this the statement

                            T1 > M, !,                       % 2.if condition
                            M1 is T1, To1 is K, From1 is V,  % statement

                            longest_asc_sublist(Xss,To1,From1,K1,T1,V1,M1).

Моя самая большая проблема заключается в том, что я не могу заставить его выйти за пределы «Xs ‹ X», как только он оценивается как false, программа завершается и возвращает false.

Итак, мои 2 вопроса:

Как я могу заставить эту программу не завершаться, когда «Xs ‹ X» ложно?

Есть ли способ реализовать это, если это так?:

(Xs < X ->
(T1 is 1, V1 is K)),

без того, чтобы это вызывало прекращение, если оно оценивается как ложное?


if-statement recursion prolog sublist tail-recursion
person sLeitner    schedule 08.12.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Простой ответ, не вдаваясь в ваш код, заключается в следующем:

(   condition
->  if condition is true
)

эквивалентно:

(   condition
->  if condition is true
;   false
)

(как вы уже сами заметили)

Что вам, вероятно, нужно:

(   condition
->  if condition is true
;   true
)

if-else then-else if-then... выглядит так:

(   if
->  then
;   else if
->  then
    % and so on
)

а два if друг за другом, конечно,

(   if
->  then
;   true
),
(   if
->  then
;   true
)

А теперь о is: если вы на самом деле хотите просто унифицировать переменную с другой, и вы не можете сделать это напрямую, просто используя то же имя переменной, то тогда вам следует унифицировать явно, используя =:

T1 = 1
person Community    schedule 08.12.2013
comment
Спасибо, это действительно помогло мне, я не знал, что могу просто сказать: иначе правда. Я все еще пытаюсь понять, как управлять всеми моими переменными до того, как будет вызвана рекурсия, но я должен быть в состоянии справиться с этим сам ^^ - person sLeitner; 08.12.2013
comment
Что ж, еще раз спасибо за помощь! Я должен признать, что не понимаю разницы между is и =, так как оператор = не позволяет мне изменять переменные, которые уже имеют значение, как и оператор is, но мне удалось обойти это, переведя эти операторы if в предложения и использование дополнительных переменных, поскольку в моем случае оба блока if изменяют разные переменные, поэтому мои операторы else теперь просто присваивают одно и то же значение новой переменной, например, T3 is T1. - person sLeitner; 09.12.2013
comment
@elefish, оператор is создает экземпляр одной переменной слева с вычисленным и полностью созданным выражением справа. Например, Y=12, Z=2, X is Y+2*Z. создаст экземпляр X с 16. Если экземпляр Y или Z не создан, произойдет ошибка. Оператор = пытается создать экземпляр обеих сторон для одного и того же термина и не вычисляет выражение. Таким образом, Y=12, Z=2, X = Y+2*Z приведет к X = 12+2*2 (эквивалентно X = +(12,*(2,2)). - person lurker; 09.12.2013