4

Is it possible to append a number to a term directly?

I.e., I can easily do something like this:

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

But is there a way (operator?) to specify something instead of '+' in the C = A + B to get "C = 1+23"?

I feel I'm asking for something strange, so here is the context. I have a list of digits, and I want to generate all expressions that can be obtained by putting '+', '-' or nothing between the digits.

Pluses and minuses are easy part:

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

But I also want to get "E = 12+3", "E = 1+23" and "E = 123". Is there an easy way to do it?

Update: the solution should be portable or at least work in B-Prolog.

Sergii Dymchenko
  • 6,890
  • 1
  • 21
  • 46
  • 1
    It seems you want to perform some systematic tests. In that case, it is preferable to define the criteria in terms of the abstract syntax tree (like, n nodes etc.) and not in terms of the concrete syntax, which is what you essentially do. – false May 09 '14 at 10:53
  • Can you clarify if you want solutions such as `(1+2)+3` (as in e.g. Carlo's answer) or `1+(2+3)` (as in my answer) or both? – Paulo Moura May 09 '14 at 13:52
  • @PauloMoura I'd prefer (1+2)+3, but any form is OK as long as it's consistently used. I mean, out of "(1+2)+3" and "1+(2+3)" only one must be in the output. – Sergii Dymchenko May 09 '14 at 16:29

5 Answers5

3

here is my bet

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.

The purpose of the verbose [N|Ns], etc is to avoid matching empty lists.

edit Here is a variation, that doesn't require maplist/3 and number_codes/2. The code it's quite similar in size...

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.

It's more efficient tough (at least on inference count), indeed here is a performance test

?- 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, ... - ...|...].

Of course, I've renamed the two versions possible_1, possible_2

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • 2
    Can you try with the performance optimization in my (edited) answer that avoids the calls to `=../2`? As you're avoiding the calls to `number_codes/2` that I'm using, your solution can be a bit faster. This is a fun problem :-) – Paulo Moura May 09 '14 at 09:30
  • 1
    @PauloMoura: your one is faster, with 15,859 inferences. While developing, I also get these terms, like `1+(2+3)`, and I managed to avoid them before posting a solution, but the original question make no clear what's the preferred behaviour about associativity/precedence... Yes, it's a fun problem :) – CapelliC May 09 '14 at 09:39
  • With the optimization I suggested for your second solution, I get 12,420 inferences. Just replace `(Op = + ; Op = -), X =.. [Op, Lx,Rx]` with `(X = (Lx + Rx); X = (Lx - Rx))`. – Paulo Moura May 09 '14 at 09:44
  • Unfortunately, avoiding `1+(2+3)` solutions seems to prevent using a tail-recursive definition for the `possible/2` predicate. – Paulo Moura May 09 '14 at 09:51
  • @PauloMoura: your suggested optimization it's very good, thanks. Sincerely, I don't get why the inference count changes so much... – CapelliC May 10 '14 at 09:56
2

How about this simple and fully portable solution:

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).

Using B-Prolog for testing:

$ 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

Regarding performance, using the same benchmark as in Carlo's answer, I get:

?- 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+ (... + ...), ... + ...|...].
Paulo Moura
  • 18,373
  • 3
  • 23
  • 33
1

This solution works without string-to-term conversions. It still depends on the SWI-Prolog predicate atom_number/2 (not sure how widely available this is). If ISO compliance is necessary, I believe it should suffice to write a custom atom_number/2 predicate using atom_codes/2 and number_codes/2. digit_appended_to_expression/3 is actually too general, since it will work with any predicate that takes a number as its second argument. 

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).

This still doesn't give an operator, because it needs a 3-place predicate, but one could use term expansion to achieve macro if it were really important.

Is it sufficient?

Shon
  • 3,989
  • 1
  • 22
  • 35
  • 1
    This is the path I started going down with the problem. – lurker May 06 '14 at 12:11
  • I really hope that there is a more compact way. – Sergii Dymchenko May 08 '14 at 18:32
  • The predicate `atom_number/2` is proprietary, not an official or de facto standard predicate. – Paulo Moura May 08 '14 at 23:24
  • I get that, but it seems (relatively) easy to write an equivalent using iso predicates. It strikes me as being handy enough to warrant inclusion in one's personal stock of predicates. Or is there some particular reason why one ought to avoid an equivalent of `atom_number/2`? (I thought I acknowledged its non-standard nature, did I fuddle the terminology?) When you say "proprietary" do you mean that someone *owns* the predicate somehow? Or just that it's specific to certain implementations (just SWI?)? Thanks for your help. – Shon May 09 '14 at 09:05
  • 1
    By "proprietary" I mean Prolog dialect specific. Nothing wrong with that per se of course, specially when, as you point out, you can define the `atom_number/2` predicate using standard predicates. – Paulo Moura May 09 '14 at 13:46
1

Here is a possible (pun intended) solution using accumulators:

%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).

The number expansion part is admittedly ugly either ways, but at least it can be portably ugly.

The output is:

| ?- 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
xxa
  • 1,258
  • 9
  • 20
  • Use of the standard `=../2` built-in predicate is **never** necessary when the first list element (the functor of the term being constructed) is bound and the other list elements can be enumerated. Calls to this predicate are expensive (not the least because they require using a temporary list that later is must be garbage-collected) and should be avoided when possible. Simply write e.g. `E = Z+XT`or replace `E` in the clause head by `Z+XT`. – Paulo Moura May 11 '14 at 11:13
  • @PauloMoura: You are right, I modified the answer accordingly. – xxa May 11 '14 at 11:24
0

I initially misunderstood your question and just approached it as a list processing exercise using DCGs. I only realized that you were trying to generate Prolog terms after I'd finished with the DCG. But I was able to get a workable solution by converting the list to a string and then the string to a term using SWI-Prolog's string handling predicates. I'd be interested to know of a more straightforward way of accomplishing this.

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 --> [-].

This version of possible/2 will generate evaluable prolog terms:

?- 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 ;
...
Shon
  • 3,989
  • 1
  • 22
  • 35
  • Yes, by converting terms to strings it's easy to do, even without DCG. But I don't want to use this way because not all Prologs have term <-> string converting predicates (initially I tried to solve the problem in B-Prolog), and also it looks very "un-prologish". – Sergii Dymchenko May 06 '14 at 03:36
  • @SergeyDymchenko But I assume you will have to, and are okay with, building atoms from your digits using `atom_concat/3`? – Shon May 06 '14 at 03:45