Функция-преемник в Прологе

В вопросе, с которым я недавно столкнулся на экзамене по логическому программированию в университете, меня попросили запрограммировать предикат Пролога odd/1, который определяет, является ли данное значение нечетным.

Предполагалось, что реализация будет использовать уже заданный предикат s/1, который будет оценивать преемника (то есть X + 1) данного элемента. Это было решение для реализации предиката odd/1:

odd(s(0)):-!. % 1 is the first odd number
odd(s(s(X))):- odd(X). % A number s(s(X)) (i.e X + 2) is odd if X is odd as well
  1. Действительно ли ! в первом выражении служит какой-либо цели? Я знаю, что это предотвращает возврат после этого момента, но нет следующих выражений? Означает ли это, что алгоритм разрешения просто останавливается на этом этапе?
  2. Я пытался реализовать предикат преемника s/1 ради практики, но не смог. (Как) Можно ли реализовать этот предикат на Прологе?

prolog successor-arithmetics
person barghest    schedule 18.03.2014    source источник
comment
Вырезание (!) делает ваше определение неполным: odd(X),X=s(s(s(0))) не выполняется, но оно должно быть успешным, как X=s(s(s(0))),odd(X)   -  person false    schedule 18.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

вот след без разреза

[trace] 21 ?- odd(s(s(s(0)))).
   Call: (6) odd(s(s(s(0))))
   Call: (7) odd(s(0))
   Exit: (7) odd(s(0))
   Exit: (6) odd(s(s(s(0))))
true ;
   Redo: (7) odd(s(0))
   Fail: (7) odd(s(0))
   Fail: (6) odd(s(s(s(0))))
false.

а здесь с разрезом

[trace] 22 ?- odd(s(s(s(0)))).
   Call: (6) odd(s(s(s(0))))
   Call: (7) odd(s(0))
   Exit: (7) odd(s(0))
   Exit: (6) odd(s(s(s(0))))
true.

Думаю, сокращение добавлено для эффективности ...

По поводу s / 1 это не предикат, а структура данных. Может быть, вы видели что-то вроде

integer(0).
integer(s(X)) :- integer(X).

это на самом деле простейшее рекурсивное определение бесконечной области (положительных) целых чисел

person CapelliC    schedule 18.03.2014