Пролог: добавить номер к термину

Можно ли добавить число к термину напрямую?

Т.е. я могу легко сделать что-то вроде этого:

?- A = 1 + 2, B = 3, C = A + B.
C = 1+2+3

Но есть ли способ (оператор?) Указать что-то вместо '+' в C = A + B получить "C = 1+23"?

Я чувствую, что прошу чего-то странного, так что вот контекст. У меня есть список цифр, и я хочу сгенерировать все выражения, которые можно получить, поставив "+", "-" или ничего между цифрами.

Плюсы и минусы являются легкой частью:

possible([X], X) :- !.
possible([A, B | Rest], E) :-
    ( H = A + B ; H = A - B ),
    possible([H | Rest], E).

?- possible([1, 2, 3], E).
E = 1+2+3 ?;
E = 1+2-3 ?;
E = 1-2+3 ?;
E = 1-2-3
yes

Но я также хочу получить "E = 12+3", "E = 1+23" и "E = 123". Есть ли простой способ сделать это?

Обновление: решение должно быть переносимым или хотя бы работать в B-Prolog.

Источник

5 ответов

Решение

Вот моя ставка

possible([N|Ns], D) :-
    digits_number([N|Ns], D).
possible([N|Ns], X) :-
    append([L|Ls], [R|Rs], [N|Ns]),
    possible([L|Ls], Lx),
    digits_number([R|Rs], Rx),
    (Op = + ; Op = -), X =.. [Op, Lx, Rx].

digits_number(Digits, N) :-
    maplist(digit_code, Digits, Codes),
    number_codes(N, Codes).
digit_code(D, C) :-
    C is D + 0'0.

Цель многословного [N|Ns] и т. Д. - избежать совпадения пустых списков.

edit Вот вариант, который не требует maplist/3 и number_codes/2. Код очень похож по размеру...

possible(Ns, D) :-
    digits_number(Ns, _, D).
possible([N|Ns], X) :-
    append([L|Ls], [R|Rs], [N|Ns]),
    possible([L|Ls], Lx),
    digits_number([R|Rs], _, Rx),
    (Op = + ; Op = -), X =.. [Op, Lx,Rx].

digits_number([Digit], 1, Digit).
digits_number([D|Ds], F, N) :-
    digits_number(Ds, G, T),
    F is G * 10,
    N is T + D * F.

Он более эффективен (по крайней мере, по количеству логических выводов), вот тест производительности

?- L=[1,2,3,4,5,6,7,8], time(findall(X,possible_1(L,X),L1)), time(findall(X,possible_2(L,X),L2)).
% 31,591 inferences, 0.017 CPU in 0.017 seconds (100% CPU, 1851600 Lips)
% 20,656 inferences, 0.017 CPU in 0.018 seconds (98% CPU, 1192235 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8],
L1 = L2, L2 = [12345678, 1+2345678, 1-2345678, 12+345678, 12-345678, 1+2+345678, 1+2-345678, ... - ... + 345678, ... - ...|...].

Конечно, я переименовал две версии возможных_1, возможных_2

Источник

Как насчет этого простого и полностью переносимого решения:

possible([Digit], Digit).
possible([Digit| Digits], Digit + RightExpression) :-
    possible(Digits, RightExpression).
possible([Digit| Digits], Digit - RightExpression) :-
    possible(Digits, RightExpression).
possible([Digit1, Digit2| Digits], Expression) :-
    Number0 is Digit1 * 10,
    Number is Number0 + Digit2,
    possible([Number| Digits], Expression).

Использование B-Prolog для тестирования:

$ bp
B-Prolog Version 8.1, All rights reserved, (C) Afany Software 1994-2014.
| ?- [possible].
consulting::possible.pl

yes
| ?- possible([1,2,3], Exp).
Exp = 1+(2+3) ?;
Exp = 1+(2-3) ?;
Exp = 1+23 ?;
Exp = 1-(2+3) ?;
Exp = 1-(2-3) ?;
Exp = 1-23 ?;
Exp = 12+3 ?;
Exp = 12-3 ?;
Exp = 123 ?;
no

Что касается производительности, используя тот же тест, что и в ответе Карло, я получаю:

?- L=[1,2,3,4,5,6,7,8], time(findall(X,possible(L,X),L1)).
% 12,037 inferences, 0.003 CPU in 0.003 seconds (93% CPU, 4223509 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8],
L1 = [1+ (2+ (3+ (4+ (5+ (6+ (7+8)))))), 1+ (2+ (3+ (4+ (5+ (6+ (7-8)))))), 1+ (2+ (3+ (4+ (5+ (6+78))))), 1+ (2+ (3+ (4+ (5+ (... - ...))))), 1+ (2+ (3+ (4+ (... + ...)))), 1+ (2+ (3+ (... + ...))), 1+ (2+ (... + ...)), 1+ (... + ...), ... + ...|...].
Источник

Вот возможное (каламбур) решение с использованием аккумуляторов:

%numberexp( D, N, XN) :- number_chars( D, DL), DL=[ DC| _], number_chars( N, NL), number_chars( XN, [ DC| NL]).
numberexp( D, N, XN) :- XN is integer( exp( log( 10)*(1+integer( log( 10, N))))*D+N).


poss( [ H], H, Z, Z).
poss( [ H| T], H, Z, E) :- poss( T, F, F, XT), E= Z+XT.
poss( [ H| T], H, Z, E) :- poss( T, F, F, XT), E= Z-XT.
poss( [ H| T], A, Z, E) :- poss( T, F, Z,  E), numberexp( H, F, A).

possible( L, E) :- poss( L, F, F, E).

Часть расширения чисел в любом случае, по общему мнению, безобразна, но, по крайней мере, она может быть уродливой.

Выход:

| ?- possible([1,2,3],E).
E = 1+(2+3) ?;
E = 1+(2-3) ?;
E = 1+23 ?;
E = 1-(2+3) ?;
E = 1-(2-3) ?;
E = 1-23 ?;
E = 12+3 ?;
E = 12-3 ?;
E = 123 ?;
no
Источник

Это решение работает без преобразования строки в термин. Это все еще зависит от предиката SWI-Prolog atom_number/2 (не уверен, насколько широко это доступно). Если необходимо соответствие ISO, я считаю, что достаточно написать собственный atom_number/2 использование предиката atom_codes/2 а также number_codes/2, digit_appended_to_expression/3 на самом деле слишком общий, поскольку он будет работать с любым предикатом, который принимает число в качестве второго аргумента.

digit_appended_to_expression(Expression, C, ExpressionWithC) :-
    Expression =.. [Operator, A, B],
    digit_concat(B, C, BC),
    ExpressionWithC =.. [Operator, A, BC].

digit_concat(A, B, AB) :-
    number(A),
    number(B),
    atom_number(A_Atom, A),
    atom_number(B_Atom, B),
    atom_concat(A_Atom, B_Atom, AB_Atom),
    atom_number(AB_Atom, AB).

possible([X], X) :- !.
possible([A, B | Rest], E) :-
    ( digit_concat(A, B, H)
    ; H = A + B
    ; H = A - B
    ; digit_appended_to_expression(A, B, H)
    ),
    possible([H | Rest], E).

Это все еще не дает оператору, потому что ему нужен трехзначный предикат, но можно использовать термин расширение для достижения макроса, если он действительно важен.

Достаточно ли этого?

Источник

Я изначально неправильно понял ваш вопрос и просто подошел к нему как к упражнению по обработке списков с использованием DCG. Я только понял, что вы пытались создать термины Пролог после того, как я закончил с DCG. Но я смог получить работоспособное решение, преобразовав список в строку, а затем строку в термин, используя предикаты обработки строк SWI-Prolog. Мне было бы интересно узнать более простой способ сделать это.

possible(Digits, AsTerm) :-
    phrase(sequence(Digits), Sequence),
    atomics_to_string(Sequence, AsString),
    term_string(AsTerm, AsString).

sequence(Ds) -->
    digits(Ds).
sequence(Ds) --> {append(First, Last, Ds)},
    digits(First), sign, sequence(Last).

digits([D]) -->
    digit(D).
digits([D|Ds]) -->
    digit(D), digits(Ds).

digit(D) --> {integer(D)},
    [D].

sign --> [+].
sign --> [-].

Эта версия возможных /2 будет генерировать оцениваемые прологи:

?- possible([1,2,3],X), Y is X.
X = Y, Y = 123 ;
X = 1+23,
Y = 24 ;
X = 1+2+3,
Y = 6 ;
X = 1+2-3,
Y = 0 ;
...
Источник
Другие вопросы по тегам