Пролог считает с использованием s(0) и p(0)

Question

Пролог считает с использованием s(0) и p(0)

У меня есть некоторые проблемы с частью моей ревизии для моего экзамена по прологу.

Мне нужно создать рекурсивное утверждение, которое будет называться упрощением /2. Пример использования будет

simplify(s(p(s(0))),Z)

что приведет к Z будучи с (0). S обозначает преемника и P предшественника. Так:s(0) это 1, s(s(0)) это 2 и p(0) -1 и т. д. p(s(p(p(0)))) было бы p(p(0)),

Код, который у меня был изначально, был

check(s(0),s(0)).
check(s(X),s(0)) :- check(X,s(s(0))).
check(p(X),s(0)) :- check(X,0).

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

3

prolog successor-arithmetics

Источник

15 май '14 в 17:34

6 ответов

Другие вопросы по тегам prolog successor-arithmetics

user220700 15 май '14 в 23:49 2014-05-15 23:49 · Answer 1 · 2014-05-15 23:49

ОК, еще одно "забавное" решение. Этот работает в ECliPSe и использует нестандартные append_strings, который является строковым "аналогом списков" append:

simplify(X, Z) :-
    term_string(X, Xstr),
    ( append_strings(Middle, End, Xstr), 
        ( 
            append_strings(Begin, "s(p(", Middle) 
        ; 
            append_strings(Begin, "p(s(", Middle) 
        ) ->
        append_strings(NewEnd, "))", End),
        append_strings(Begin, NewEnd, Zstr),
        term_string(Ztemp, Zstr),
        simplify(Ztemp, Z)
    ;
      Z = X
    ).

user220700 15 май '14 в 19:37 2014-05-15 19:37 · Answer 2 · 2014-05-15 19:37

Моя попытка:

simplify(X, Z) :-
    simplify(X, 0, Z).
simplify(0, Z, Z).
simplify(s(X), 0, Z) :- simplify(X, s(0), Z).
simplify(p(X), 0, Z) :- simplify(X, p(0), Z).
simplify(p(X), s(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), p(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), s(Y), Z) :- simplify(X, s(s(Y)), Z).
simplify(p(X), p(Y), Z) :- simplify(X, p(p(Y)), Z).

Обновление - более короткая версия:

simplify(X, Z) :-
    simplify(X, 0, Z).
simplify(0, Z, Z).
simplify(p(X), s(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), p(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), Y, Z) :- Y \= p(_), simplify(X, s(Y), Z).
simplify(p(X), Y, Z) :- Y \= s(_), simplify(X, p(Y), Z).

Некоторые тесты:

?- simplify(s(p(s(0))), Z).
Z = s(0) 

?- simplify(p(s(p(p(0)))), Z).
Z = p(p(0)) 

?- simplify(p(p(s(s(0)))), Z).
Z = 0

user772868 15 май '14 в 18:14 2014-05-15 18:14 · Answer 3 · 2014-05-15 18:14

z(0).
z(s(X)) :-
   z(X).
z(p(X)) :-
   z(X).

z_canonized(Z, C) :-
   z_canonized(Z, 0, C).

z_canonized(0, C,C).
z_canonized(s(N), C0,C) :-
   z_succ(C0,C1),
   z_canonized(N, C1,C).
z_canonized(p(N), C0,C) :-
   z_pred(C0,C1),
   z_canonized(N, C1,C).

z_succ(0,s(0)).
z_succ(s(X),s(s(X))). % was: z_succ(X,s(X)) :- ( X = 0 ; X = s(_) ).
z_succ(p(X),X).

z_pred(0,p(0)).
z_pred(p(X),p(p(X))).
z_pred(s(X),X).

3

Источник

user772868 15 май '14 в 18:14

user925196 15 май '14 в 20:03 2014-05-15 20:03 · Answer 4 · 2014-05-15 20:03

Это мой ответ:

simplify(X, Z) :- simplify(X, 0, 0, Z).
simplify(0, 0, X, X).
simplify(0, X, 0, X) :- X \= 0.
simplify(0, p(X), s(Y), Z) :- simplify(0, X, Y, Z).
simplify(p(X), P, S, Z) :- simplify(X, p(P), S, Z).
simplify(s(X), P, S, Z) :- simplify(X, P, s(S), Z).

Я делю структуру ввода на две цепочки pс и sи затем я удаляю одну за другой из обеих цепей. Когда один из них заканчивается, другой становится результатом операции. Я думаю, что это довольно эффективно.

user634629 15 май '14 в 22:27 2014-05-15 22:27 · Answer 5 · 2014-05-15 22:27

Еще один ответ, закодированный для шутки над этим. Сначала он упрощает выражение до целого числа, а затем преобразует результат в p(...) для отрицательных целых чисел, s(...) для положительных целых чисел (исключая ноль), и 0 за 0, Стандарт sign/1 арифметическая функция используется для использования индексации первого аргумента.

simplify(Expression, Result) :-
    simplify(Expression, 0, Result0),
    Sign is sign(Result0),
    convert(Sign, Result0, Result).

simplify(0, Result, Result).
simplify(s(X), Result0, Result) :-
    Result1 is Result0 + 1,
    simplify(X, Result1, Result).
simplify(p(X), Result0, Result) :-
    Result1 is Result0 - 1,
    simplify(X, Result1, Result).

convert(-1, N, p(Result)) :-
    N2 is N + 1,
    Sign is sign(N2),
    convert(Sign, N2, Result).
convert(0, _, 0).
convert(1, N, s(Result)) :-
    N2 is N - 1,
    Sign is sign(N2),
    convert(Sign, N2, Result).

user980550 15 май '14 в 23:05 2014-05-15 23:05 · Answer 6 · 2014-05-15 23:05

Я был вдохновлен предложением Пауло сделать вариант подхода "Посчитай p и s":

simplify(Exp, Simp) :-
    exp_count(Exp, Count),
    exp_count(Simp, Count).

exp_count(Exp, C) :-
    exp_count(Exp, 0, C).

exp_count(s(X), A, C) :-
    (   nonvar(C)
    ->  A < C
    ;   true
    ),
    A1 is A + 1,
    exp_count(X, A1, C).
exp_count(p(X), A, C) :-
    (   nonvar(C)
    ->  A > C
    ;   true
    ),
    A1 is A - 1,
    exp_count(X, A1, C).
exp_count(0, C, C).