123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998 |
- %% -*- Mode: Prolog -*-
- %% vim: set softtabstop=4 shiftwidth=4 tabstop=4 expandtab:
- /**
- *
- * polimani.pl
- *
- * Assignment 1 - Polynomial Manipulator
- * Programming in Logic - DCC-FCUP
- *
- * Diogo Peralta Cordeiro
- * up201705417@fc.up.pt
- *
- * Hugo David Cordeiro Sales
- * up201704178@fc.up.pt
- *
- *********************************************
- * Follows 'Coding guidelines for Prolog' *
- * https://doi.org/10.1017/S1471068411000391 *
- *********************************************/
- /*
- * Import the Constraint Logic Programming over Finite Domains library
- * Essentially, this library improves the way Prolog deals with integers,
- * allowing more predicates to be reversible.
- * For instance, number(N) is always false, which prevents the
- * reversing of a predicate.
- */
- :- use_module(library(clpfd)).
- /*
- * Import Constraint Logic Programming for Reals library, which is somewhat
- * similar to clpfd, but for real numbers
- */
- :- use_module(library(clpr)).
- /*******************************
- * USER INTERFACE *
- *******************************/
- /*
- poly2list/2 transforms a list representing a polynomial (second
- argument) into a polynomial represented as an expression (first
- argument) and vice-versa.
- */
- poly2list(P, L) :-
- is_polynomial_valid_in_predicate(P, "poly2list"),
- polynomial_to_list(P, L),
- !.
- /*
- simpolylist/2 simplifies a polynomial represented as a list into
- another polynomial as a list.
- */
- simpoly_list(L, S) :-
- is_polynomial_as_list_valid_in_predicate(L, "simpoly_list"),
- simplify_polynomial_as_list(L, S),
- !.
- /*
- simpoly/2 simplifies a polynomial represented as an expression
- as another polynomial as an expression.
- */
- simpoly(P, S) :-
- is_polynomial_valid_in_predicate(P, "simpoly"),
- simplify_polynomial(P, S),
- !.
- /*
- scalepoly/3 multiplies a polynomial represented as an expression by a scalar
- resulting in a second polynomial. The two first arguments are assumed to
- be ground. The polynomial resulting from the sum is in simplified form.
- */
- scalepoly(P1, C, S) :-
- is_polynomial_valid_in_predicate(P1, "scalepoly"),
- is_number_in_predicate(C, "scalepoly"),
- scale_polynomial(P1, C, S),
- !.
- %% Tests:
- %% ?- scalepoly(3*x*z+2*z, 4, S).
- %@ S = 12*x*z+8*z.
- %% ?- scalepoly(3*x*z+2*z, 2, S).
- %@ S = 6*x*z+4*z.
- /*
- addpoly/3 adds two polynomials as expressions resulting in a
- third one. The two first arguments are assumed to be ground.
- The polynomial resulting from the sum is in simplified form.
- */
- addpoly(P1, P2, S) :-
- is_polynomial_valid_in_predicate(P1, "addpoly"),
- is_polynomial_valid_in_predicate(P2, "addpoly"),
- add_polynomial(P1, P2, S),
- !.
- %% Tests:
- %% ?- addpoly(3 + x, 3 - x, S).
- %@ S = 6.
- %% is_polynomial_valid_in_predicate(+T, +F) is det
- %
- % Returns true if valid polynomial, fails with UI message otherwise.
- % The failure message reports which polynomial is invalid and in which
- % predicate the problem ocurred.
- %
- is_polynomial_valid_in_predicate(P, _) :-
- %% If P is a valid polynomial, return true
- polynomial(P),
- !.
- is_polynomial_valid_in_predicate(P, F) :-
- %% Otherwise, write the polynomial and fails
- write("Invalid polynomial in "),
- write(F),
- write(": "),
- write(P),
- fail.
- %% Tests:
- %% ?- is_polynomial_valid_in_predicate(1-x, "Test").
- %@ true.
- %% ?- is_polynomial_valid_in_predicate(a*4-0*x, "Test").
- %@ Invalid polynomial in Test: a*4-0*x
- %@ false.
- %% is_polynomial_as_list_valid_in_predicate(+L, +F) is det
- %
- % Returns true if the polynomial represented as list is valid,
- % fails with UI message otherwise.
- % The failure message reports which polynomial is invalid and
- % in which predicate the problem ocurred.
- %
- is_polynomial_as_list_valid_in_predicate(L, F) :-
- %% If L is a valid polynomial, return true
- list_to_polynomial(L, P),
- is_polynomial_valid_in_predicate(P, F).
- %% Tests:
- %% ?- is_polynomial_as_list_valid_in_predicate([1], "Test").
- %@ true.
- %% ?- is_polynomial_as_list_valid_in_predicate([0*x, a*4], "Test").
- %@ Invalid polynomial in Test: a*4+0*x
- %@ false.
- %% is_number_in_predicate(+C:number, +F:string) is det
- %
- % Validates that C is a number or prints F and it then it
- %
- is_number_in_predicate(C, _) :-
- number(C),
- !.
- is_number_in_predicate(C, F) :-
- %% Writes the argument and fails
- write("Invalid number in "),
- write(F),
- write(": "),
- write(C),
- fail.
- /*******************************
- * NLP *
- *******************************/
- polyplay :-
- write("> "),
- read(R),
- (
- R = bye,
- write("See ya")
- ;
- (
- nlp_understand(R, P, I),
- writeln("That's trivial:"),
- nlp_compute(P, I)
- ;
- writeln("I didn't understand what you want.")
- ),
- polyplay
- ).
- nlp_understand(R,P,I) :-
- (
- R = simplify_x_squared,
- P = simplify,
- I = x^2
- ;
- fail
- ).
- nlp_compute(simplify, P) :-
- simplify_polynomial(P, O),
- writeln(O).
- nlp_compute(_,_) :-
- fail.
- parse_digit(zero, 0).
- parse_digit(one, 1).
- parse_digit(two, 2).
- parse_digit(three, 3).
- parse_digit(four, 4).
- parse_digit(five, 5).
- parse_digit(six, 6).
- parse_digit(seven, 7).
- parse_digit(eight, 8).
- parse_digit(nine, 9).
- parse_digit(ten, 10).
- parse_digit(eleven, 11).
- parse_digit(twelve, 12).
- parse_digit(thirteen, 13).
- parse_digit(fourteen, 14).
- parse_digit(fifteen, 15).
- parse_digit(sixteen, 16).
- parse_digit(seventeen, 17).
- parse_digit(eighteen, 18).
- parse_digit(nineteen, 19).
- parse_digit(twenty, 20).
- parse_digit(thirty, 30).
- parse_digit(forty, 40).
- parse_digit(fifty, 50).
- parse_digit(sixty, 60).
- parse_digit(seventy, 70).
- parse_digit(eighty, 80).
- parse_digit(ninety, 90).
- parse_number([],0).
- parse_number([N|L], X) :-
- parse_digit(N, X1),
- parse_number(L, X2),
- X is X1 + X2.
- /*******************************
- * BACKEND *
- *******************************/
- %% polynomial_variable_list(-List) is det
- %
- % List of possible polynomial variables
- %
- polynomial_variable_list([x, y, z]).
- %% polynomial_variable(?X:atom) is semidet
- %
- % Returns true if X is a polynomial variable, false otherwise.
- %
- polynomial_variable(X) :-
- polynomial_variable_list(V),
- member(X, V).
- %% Tests:
- %% ?- polynomial_variable(x).
- %@ true .
- %% ?- polynomial_variable(a).
- %@ false.
- %% power(+X:atom) is semidet
- %
- % Returns true if X is a power term, false otherwise.
- %
- power(P^N) :-
- %% CLPFD comparison. Reversible
- N #>= 1,
- polynomial_variable(P).
- power(X) :-
- polynomial_variable(X).
- %% Tests:
- %% ?- power(x).
- %@ true .
- %% ?- power(a).
- %@ false.
- %% ?- power(x^1).
- %@ true .
- %% ?- power(x^3).
- %@ true .
- %% ?- power(x^(-3)).
- %@ false.
- %% ?- power(-x).
- %@ false.
- %% ?- power(X).
- %@ X = x^_462546,
- %@ _462546 in 1..sup ;
- %@ X = y^_462546,
- %@ _462546 in 1..sup ;
- %@ X = z^_462546,
- %@ _462546 in 1..sup ;
- %@ X = x ;
- %@ X = y ;
- %@ X = z.
- %% term(+N:atom) is semidet
- %
- % Returns true if N is a term, false otherwise.
- %
- term(N) :-
- % If N is not a free variable
- nonvar(N),
- % Assert it as a number
- number(N).
- term(N) :-
- % If N is a free variable and not compound
- not(compound(N)),
- var(N),
- % Assert it must be between negative and positive infinity
- % This uses the CLPR library, which makes this reversible,
- % whereas `number(N)` is always false, since it only succeeds
- % if the argument is bound (to a integer or float)
- {N >= 0; N < 0}.
- term(X) :-
- power(X).
- term(-X) :-
- power(X).
- term(L * R) :-
- term(L),
- term(R).
- %% Tests:
- %% ?- term(2*x^3).
- %@ true .
- %% ?- term(x^(-3)).
- %@ false.
- %% ?- term(a).
- %@ false.
- %% ?- term(-1*x).
- %@ true .
- %% ?- term(-x).
- %@ true .
- %% ?- term((-3)*x^2).
- %@ true .
- %% ?- term(3.2*x).
- %@ true .
- %% ?- term(-x*(-z)).
- %@ true .
- %% ?- term(X).
- %@ {X>=0.0} ;
- %@ {X<0.0} ;
- %@ X = x^_111514,
- %@ _111514 in 1..sup ;
- %@ X = y^_111514,
- %@ _111514 in 1..sup ;
- %@ X = z^_111514,
- %@ _111514 in 1..sup ;
- %@ X = x ;
- %@ X = y ;
- %@ X = z ;
- %@ X = -x^_111522,
- %@ _111522 in 1..sup ;
- %@ X = -y^_111522,
- %@ _111522 in 1..sup ;
- %@ X = -z^_111522,
- %@ _111522 in 1..sup ;
- %@ X = -x ;
- %@ X = -y ;
- %@ X = -z ;
- %% polynomial(+M:atom) is semidet
- %
- % Returns true if polynomial, false otherwise.
- %
- polynomial(M) :-
- %% A polynomial is either a term
- term(M).
- polynomial(L + R) :-
- %% Or a sum of terms
- polynomial(L),
- term(R).
- polynomial(L - R) :-
- %% Or a subtraction of terms
- polynomial(L),
- term(R).
- %% Tests:
- %% ?- polynomial(x).
- %@ true .
- %% ?- polynomial(x^3).
- %@ true .
- %% ?- polynomial(3*x^7).
- %@ true .
- %% ?- polynomial(2 + 3*x + 4*x*y^3).
- %@ true .
- %% ?- polynomial(2 - 3*x + 4*x*y^3).
- %@ true .
- %% ?- polynomial(a).
- %@ false.
- %% ?- polynomial(x^(-3)).
- %@ false.
- %% ?- polynomial(-x + 3).
- %@ true .
- %% ?- polynomial(-x - -z).
- %@ true .
- %% power_to_canon(+T:atom, -T^N:atom) is semidet
- %
- % Returns a canon power term.
- %
- power_to_canon(T^N, T^N) :-
- polynomial_variable(T),
- % CLP(FD) operator to ensure N is different from 1,
- % in a reversible way
- N #\= 1.
- power_to_canon(T, T^1) :-
- polynomial_variable(T).
- %% Tests:
- %% ?- power_to_canon(x, X).
- %@ X = x^1 .
- %% ?- power_to_canon(-x, X).
- %@ false.
- %@ X = -1*x^1 .
- %% ?- power_to_canon(X, x^1).
- %@ X = x .
- %% ?- power_to_canon(X, x^4).
- %@ X = x^4 .
- %% ?- power_to_canon(X, a^1).
- %@ false.
- %% ?- power_to_canon(X, x^(-3)).
- %@ X = x^ -3 .
- %% ?- power_to_canon(X, -1*x^1).
- %@ X = -x .
- %% term_to_list(?T, ?List) is semidet
- %
- % Converts a term to a list of its monomials and vice versa.
- % Can verify if term and monomials list are compatible.
- %
- term_to_list(L * N, [N | TS]) :-
- number(N),
- term_to_list(L, TS).
- term_to_list(L * P, [P2 | TS]) :-
- power(P),
- power_to_canon(P, P2),
- term_to_list(L, TS).
- term_to_list(L * -P, [-P2 | TS]) :-
- power(P),
- power_to_canon(P, P2),
- term_to_list(L, TS).
- term_to_list(N, [N]) :-
- number(N).
- term_to_list(P, [P2]) :-
- power(P),
- power_to_canon(P, P2).
- term_to_list(-P, [-P2]) :-
- power(P),
- power_to_canon(P, P2).
- %% Tests:
- %% ?- term_to_list(1, X).
- %@ X = [1] .
- %% ?- term_to_list(-1, X).
- %@ X = [-1] .
- %% ?- term_to_list(x, X).
- %@ X = [x^1] .
- %% ?- term_to_list(-x, X).
- %@ X = [-x^1] .
- %% ?- term_to_list(2 * 3, X).
- %@ X = [3, 2] .
- %% ?- term_to_list(1*2*y*z*23*x*y*x^3*x, X).
- %@ X = [x^1, x^3, y^1, x^1, 23, z^1, y^1, 2, 1] .
- %% ?- term_to_list(1*2*y*z*23*x*y*(-1), X).
- %@ X = [-1, y^1, x^1, 23, z^1, y^1, 2, 1] .
- %% ?- term_to_list(X, [-1]).
- %@ X = -1 .
- %% ?- term_to_list(X, [x^1, -1]).
- %@ X = -1*x .
- %% ?- term_to_list(X, [-x^1]).
- %@ X = -x .
- %% ?- term_to_list(X, [y^1, x^1]).
- %@ X = x*y .
- %% ?- term_to_list(X, [x^4]).
- %@ X = x^4 .
- %% ?- term_to_list(X, [y^6, z^2, x^4]).
- %@ X = x^4*z^2*y^6 .
- %% ?- term_to_list(X, [y^6, z^2, x^4, -2]).
- %@ X = -2*x^4*z^2*y^6 .
- %% ?- term_to_list(X, [x^1, 0]).
- %@ X = 0*x .
- %% ?- term_to_list(X, [y^1, -2]).
- %@ X = -2*y .
- %% simplify_term(+Term_In:term, ?Term_Out:term) is det
- %
- % Simplifies a given term.
- % This function can also be be used to verify if
- % a term is simplified.
- %
- simplify_term(Term_In, Term_Out) :-
- term_to_list(Term_In, L),
- %% Sort the list of numbers and power to group them,
- %% simplifying the job of `join_similar_parts_of_term`
- sort(0, @=<, L, L2),
- (
- %% If there's a 0 in the list, then the whole term is 0
- member(0, L2),
- Term_Out = 0
- ;
- %% Otherwise
- (
- %% If there's only one element, then the term was already simplified
- %% This is done so that the `exclude` following doesn't remove all ones
- length(L2, 1),
- Term_Out = Term_In
- ;
- %% Remove all remaining ones
- exclude(==(1), L2, L3),
- join_similar_parts_of_term(L3, L4),
- %% Reverse the list, since the following call gives the result in the
- %% reverse order otherwise
- reverse(L4, L5),
- term_to_list(Term_Out, L5)
- )
- ),
- % First result is always the most simplified form.
- !.
- %% Tests:
- %% ?- simplify_term(1, X).
- %@ X = 1.
- %% ?- simplify_term(x, X).
- %@ X = x.
- %% ?- simplify_term(2*y*z*x^3*x, X).
- %@ X = 2*x^4*y*z.
- %% ?- simplify_term(1*y*z*x^3*x, X).
- %@ X = x^4*y*z.
- %% ?- simplify_term(0*y*z*x^3*x, X).
- %@ X = 0.
- %% ?- simplify_term(6*y*z*7*x*y*x^3*x, X).
- %@ X = 42*x^5*y^2*z.
- %% ?- simplify_term(-x, X).
- %@ X = -x.
- %% ?- simplify_term(-x*y*(-z)*3, X).
- %@ X = 3* -x* -z*y.
- %% ?- simplify_term(a, X).
- %@ false.
- %% ?- simplify_term(x^(-3), X).
- %@ false.
- %% join_similar_parts_of_term(+List, -List) is det
- %
- % Combine powers of the same variable in the given list.
- % Requires that the list be sorted.
- %
- join_similar_parts_of_term([P1, P2 | L], L2) :-
- %% If both symbols are powers
- power(P1),
- power(P2),
- %% Decompose them into their parts
- B^N1 = P1,
- B^N2 = P2,
- %% Sum the exponent
- N is N1 + N2,
- join_similar_parts_of_term([B^N | L], L2),
- % First result is always the most simplified form.
- !.
- join_similar_parts_of_term([N1, N2 | L], L2) :-
- %% If they are both numbers
- number(N1),
- number(N2),
- %% Multiply them
- N is N1 * N2,
- join_similar_parts_of_term([N | L], L2),
- % First result is always the most simplified form.
- !.
- join_similar_parts_of_term([X | L], [X | L2]) :-
- %% Otherwise consume one element and recurse
- join_similar_parts_of_term(L, L2),
- % First result is always the most simplified form.
- !.
- join_similar_parts_of_term([], []).
- %% Tests:
- %% ?- join_similar_parts_of_term([3], T).
- %@ T = [3].
- %% ?- join_similar_parts_of_term([x^2], T).
- %@ T = [x^2].
- %% ?- join_similar_parts_of_term([x^1, x^1, x^1, x^1], T).
- %@ T = [x^4].
- %% ?- join_similar_parts_of_term([2, 3, x^1, x^2], T).
- %@ T = [6, x^3].
- %% ?- join_similar_parts_of_term([2, 3, x^1, x^2, y^1, y^6], T).
- %@ T = [6, x^3, y^7].
- %% ?- join_similar_parts_of_term([2, 3, -x^1, -x^2], T).
- %@ T = [6, -x^1, -x^2].
- %% simplify_polynomial(+P:atom, -P2:atom) is det
- %
- % Simplifies a polynomial.
- %
- simplify_polynomial(0, 0) :-
- % 0 is already fully simplified. This is an
- % exception to the following algorithm
- !.
- simplify_polynomial(P, P2) :-
- polynomial_to_list(P, L),
- simplify_polynomial_as_list(L, L2),
- list_to_polynomial(L2, P2),
- %% The first result is the most simplified one
- !.
- %% Tests:
- %% ?- simplify_polynomial(1, X).
- %@ X = 1.
- %% ?- simplify_polynomial(0, X).
- %@ X = 0.
- %% ?- simplify_polynomial(x, X).
- %@ X = x.
- %% ?- simplify_polynomial(x*x, X).
- %@ X = x^2.
- %% ?- simplify_polynomial(2 + 2, X).
- %@ X = 2*2.
- %% ?- simplify_polynomial(x + x, X).
- %@ X = 2*x.
- %% ?- simplify_polynomial(0 + x*x, X).
- %@ X = x^2.
- %% ?- simplify_polynomial(x^2*x + 3*x^3, X).
- %@ X = 4*x^3.
- %% ?- simplify_polynomial(x^2*x + 3*x^3 + x^3 + x*x*x, X).
- %@ X = 6*x^3.
- %% ?- simplify_polynomial(x^2*x + 3*x^3 + x^3 + x*x*4 + z, X).
- %@ X = 5*x^3+4*x^2+z.
- %% ?- simplify_polynomial(x^2*x + 3*x^3 - x^3 - x*x*4 + z, X).
- %@ X = 3*x^3-4*x^2+z.
- %% ?- simplify_polynomial(x + 1 + x, X).
- %@ X = 2*x+1.
- %% ?- simplify_polynomial(x + 1 + x + 1 + x + 1 + x, X).
- %@ X = 4*x+3.
- %% simplify_polynomial_as_list(+L1:List,-L3:List) is det
- %
- % Simplifies a polynomial represented as a list.
- %
- simplify_polynomial_as_list(L, L13) :-
- %% Convert each term to a list
- maplist(term_to_list, L, L2),
- %% Sort each sublist so that the next
- %% sort gives the correct results
- maplist(sort(0, @>=), L2, L3),
- %% Sort the outer list
- sort(0, @>=, L3, L4),
- %% For each of the parts of the terms, join them
- maplist(join_similar_parts_of_term, L4, L5),
- %% Sort each of the sublists
- %% Done so the next call simplifies has less work
- maplist(sort(0, @=<), L5, L6),
- join_similar_terms(L6, L7),
- %% Exclude any sublist that includes a 0 (such as the
- %% equivalent to the term 0*x)
- exclude(member(0), L7, L8),
- %% Reverse each sublist, because the next call
- %% reverses the result
- maplist(reverse, L8, L9),
- maplist(term_to_list, L10, L9),
- %% Delete any 0 from the list
- delete(L10, 0, L11),
- %% Sort list converting back gives the result in the correct order
- sort(0, @=<, L11, L12),
- (
- %% If the list is empty, the result is a list with 0
- L12 = [], L13 = [0]
- ;
- %% Otherwise, this is the result
- L13 = L12
- ).
- %% Tests:
- %% ?- simplify_polynomial_as_list([x, 1, x^2, x*y, 3*x^2, 4*x], L).
- %@ L = [1, 4*x^2, 5*x, x*y] .
- %% ?- simplify_polynomial_as_list([1, x^2, x*y, 3*x^2, -4, -1*x], L).
- %@ L = [-3, -1*x, 4*x^2, x*y] .
- %% ?- simplify_polynomial_as_list([0*x, 0], L).
- %@ L = [0] .
- %% join_similar_terms(+P:List, -P2:List) is det
- %
- % Joins similar sublists representing terms by using
- % `add_terms` to check if they can be merged and perform
- % the addition. Requires the list of list be sorted with
- % `maplist(sort(0, @>=), L, L2),
- % sort(0, @>=, L2, L3)`
- % and that the sublists to be sorted with
- % `sort(0, @=<)` since that is inherited from `add_terms`.
- %
- join_similar_terms([TL, TR | L], L2) :-
- %% Check if terms can be added and add them
- add_terms(TL, TR, T2),
- %% Recurse, accumulation on the first element
- join_similar_terms([T2 | L], L2),
- %% Give only first result. Red cut
- !.
- join_similar_terms([X | L], [X | L2]) :-
- %% If a pair of elements can't be added, skip one
- %% and recurse
- join_similar_terms(L, L2),
- %% Give only first result. Red cut
- !.
- join_similar_terms([], []).
- %% Tests:
- %% ?- join_similar_terms([[2, x^3], [3, x^3], [x^3]], L).
- %@ L = [[6, x^3]].
- %% term_to_canon(+T:List, -T2:List) is det
- %
- % Adds the coefficient of the term as the first element of the list
- %
- %% Special cases to make this predicate reversible
- term_to_canon([1], [1]) :-
- !.
- term_to_canon(L2, [1 | L]) :-
- nonvar(L),
- L2 = L,
- !.
- term_to_canon([-1], [-1]) :-
- !.
- term_to_canon([-P | L2], [-1, P | L]) :-
- nonvar(L),
- L2 = L,
- !.
- term_to_canon([N2 | L], [N | L]) :-
- number(N),
- N2 = N,
- !.
- %% Normal case
- term_to_canon(L, [N | L2]) :-
- term_to_canon_with_coefficient(N, L, L2),
- !.
- %% Tests:
- %% ?- term_to_canon([2], T).
- %@ T = [2].
- %% ?- term_to_canon([-x], T).
- %@ T = [-1, x].
- %% ?- term_to_canon([-x^3], T).
- %@ T = [-1, x^3].
- %% ?- term_to_canon([x^1], T).
- %@ T = [1, x^1].
- %% ?- term_to_canon([x^3], T).
- %@ T = [1, x^3].
- %% ?- term_to_canon([x^3, z], T).
- %@ T = [1, x^3, z].
- %% ?- term_to_canon([2, x^3], T).
- %@ T = [2, x^3].
- %% ?- term_to_canon([2, -x^3], T).
- %@ T = [-2, x^3].
- %% ?- term_to_canon([2, -x^3, -z], T).
- %@ T = [2, x^3, z].
- %% ?- term_to_canon(L, [-1]).
- %@ L = [-1].
- %% ?- term_to_canon(L, [1]).
- %@ L = [1].
- %% ?- term_to_canon(L, [-2]).
- %@ L = [-2].
- %% ?- term_to_canon(L, [-2, x]).
- %@ L = [-2, x].
- %% ?- term_to_canon(L, [1, x]).
- %@ L = [x].
- %% ?- term_to_canon(L, [-1, x]).
- %@ L = [-x].
- %% ?- term_to_canon(L, [1, x, z, y]).
- %@ L = [x, z, y].
- %% ?- term_to_canon(L, [-1, x, z, y]).
- %@ L = [-x, z, y].
- %% term_to_canon_with_coefficient(-N:number, +L:List, -L2:List) is semidet
- %
- % Calculates the coefficient of the term and removes negations of powers,
- % accumulating the results in N
- %
- term_to_canon_with_coefficient(N, [N2 | TS], TS2) :-
- number(N2),
- term_to_canon_with_coefficient(N3, TS, TS2),
- N is N2 * N3,
- !.
- term_to_canon_with_coefficient(N, [P | TS], [P2 | TS2]) :-
- sign_of_power(P, N2 * P2),
- term_to_canon_with_coefficient(N3, TS, TS2),
- N is N2 * N3,
- !.
- term_to_canon_with_coefficient(N, [], []) :-
- nonvar(N);
- N = 1.
- %% Tests:
- %% ?- term_to_canon_with_coefficient(N, [x], L).
- %@ N = 1,
- %@ L = [x].
- %% ?- term_to_canon_with_coefficient(N, [x, x^2, 2], L).
- %@ N = 2,
- %@ L = [x^1, x^2].
- %% ?- term_to_canon_with_coefficient(N, [x, x^2, 2, 4, z], L).
- %@ N = 8,
- %@ L = [x, x^2, z].
- %% ?- term_to_canon_with_coefficient(N, [x, x^2, 2, 4, -z], L).
- %@ N = -8,
- %@ L = [x, x^2, z].
- %% ?- term_to_canon_with_coefficient(N, [x, -x^2, 2, 4, -z], L).
- %@ N = 8,
- %@ L = [x, x^2, z].
- %% ?- term_to_canon_with_coefficient(N, L, [x]).
- %@ N = 1,
- %@ L = [x].
- %% ?- term_to_canon_with_coefficient(N, L, [1]).
- %@ N = 1,
- %@ L = [1].
- %% ?- term_to_canon_with_coefficient(N, L, [2]).
- %@ N = 1,
- %@ L = [2].
- %% sign_of_power(P:power, P:term) is det
- %
- % If there isn't a leading minus, multiplies the power by 1,
- % otherwise by a -1. This way it prefers the positive version.
- % Not idempotent
- %
- sign_of_power(P, 1*P) :-
- %% If P can't unify with a minus followed by an unnamed variable
- P \= -_,
- !.
- sign_of_power(-P, -1*P).
- %% Tests:
- %% ?- sign_of_power(x, X).
- %@ X = 1*x.
- %% ?- sign_of_power(-x, X).
- %@ X = -1*x.
- %% ?- sign_of_power(X, 1*x).
- %@ X = x.
- %% ?- sign_of_power(X, -1*x).
- %@ X = -x.
- %% add_terms(+L:List, +R:List, -Result:List) is det
- %
- % Adds two terms represented as list by adding
- % the coeficients if the power is the same.
- % Returns false if they can't be added
- % Requires the list of terms to be simplified.
- %
- add_terms([NL | TL], [NR | TR], [N2 | TL2]) :-
- %% Convert each term to a canon form. This ensures they
- %% have a number in front, so it can be added
- term_to_canon([NL | TL], [NL2 | TL2]),
- term_to_canon([NR | TR], [NR2 | TR2]),
- %% If the rest of the term is the same
- TL2 == TR2,
- %% Add the coeficients
- N2 is NL2 + NR2.
- %% Tests
- %% ?- add_terms([1], [1], R).
- %@ R = [2].
- %% ?- add_terms([x], [x], R).
- %@ R = [2, x].
- %% ?- add_terms([2, x^3], [x^3], R).
- %@ R = [3, x^3].
- %% ?- add_terms([2, x^3], [3, x^3], R).
- %@ R = [5, x^3].
- %% ?- add_terms([2, x^3], [3, x^2], R).
- %@ false.
- %% polynomial_to_list(+P:polynomial, -L:List) is det
- %
- % Converts a polynomial in a list.
- %
- polynomial_to_list(L - T, [T2 | LS]) :-
- term(T),
- negate_term(T, T2),
- polynomial_to_list(L, LS),
- !.
- polynomial_to_list(L + T, [T | LS]) :-
- term(T),
- polynomial_to_list(L, LS),
- !.
- polynomial_to_list(T, [T]) :-
- term(T),
- !.
- %% Tests:
- %% ?- polynomial_to_list(2, S).
- %@ S = [2].
- %% ?- polynomial_to_list(x^2, S).
- %@ S = [x^2].
- %% ?- polynomial_to_list(x^2 + x^2, S).
- %@ S = [x^2, x^2].
- %% ?- polynomial_to_list(2*x^2+5+y*2, S).
- %@ S = [y*2, 5, 2*x^2].
- %% ?- polynomial_to_list(2*x^2+5-y*2, S).
- %@ S = [-2*y, 5, 2*x^2].
- %% ?- polynomial_to_list(2*x^2-5-y*2, S).
- %@ S = [-2*y, -5, 2*x^2].
- %% list_to_polynomial(+L:List, -P:Polynomial) is det
- %
- % Converts a list in a polynomial.
- % An empty list will return false.
- %
- list_to_polynomial([T1|T2], P) :-
- % Start recursive calls until we are in the
- % end of the list. We know that the `-` will
- % always be at the left of a term.
- list_to_polynomial(T2, L1),
- (
- % If this is a negative term
- term_string(T1, S1),
- string_chars(S1, [First|_]),
- First = -,
- % Concat them
- term_string(L1, S2),
- string_concat(S2,S1,S3),
- term_string(P, S3)
- ;
- % Otherwise sum them
- P = L1+T1
- ),
- % The others computations are semantically meaningless
- !.
- list_to_polynomial([T], T).
- %% Tests:
- %% ?- list_to_polynomial([1, x, x^2], P).
- %@ P = x^2+x+1.
- %% ?- list_to_polynomial([-1, -x, -x^2], P).
- %@ P = -x^2-x-1.
- %% ?- list_to_polynomial([1, -x, x^2], P).
- %@ P = x^2-x+1.
- %% ?- list_to_polynomial([x^2, x, 1], P).
- %@ P = 1+x+x^2.
- %% ?- list_to_polynomial([a,-e], P).
- %@ P = -e+a.
- %% ?- list_to_polynomial([], P).
- %@ false.
- %% ?- list_to_polynomial([a], P).
- %@ P = a.
- %% negate_term(T, T2) is det
- %
- % Negate the coeficient of a term and return the negated term.
- %
- negate_term(T, T2) :-
- term_to_list(T, L),
- %% Ensure there is a coeficient
- term_to_canon(L, L2),
- [N | R] = L2,
- %% (-)/1 is an operator, needs to be evaluated, otherwise
- %% it gives a symbolic result, which messes with further processing
- N2 is -N,
- %% Convert the term back from canonic form
- term_to_canon(L3, [N2 | R]),
- %% Reverse the order of the list, because converting
- %% implicitly reverses it
- reverse(L3, L4),
- term_to_list(T2, L4),
- !.
- %% Tests:
- %% ?- negate_term(1, R).
- %@ R = -1.
- %% ?- negate_term(x, R).
- %@ R = -x.
- %% ?- negate_term(-x, R).
- %@ R = x.
- %% ?- negate_term(x^2, R).
- %@ R = -x^2.
- %% ?- negate_term(3*x*y^2, R).
- %@ R = -3*y^2*x.
- %% scale_polynomial(+P:Polynomial,+C:Constant,-S:Polynomial) is det
- %
- % Multiplies a polynomial by a scalar.
- %
- scale_polynomial(P, C, S) :-
- polynomial_to_list(P, L),
- %% Convert each term to a list
- maplist(term_to_list, L, L2),
- %% Canonize terms
- maplist(term_to_canon, L2, L3),
- %% Append C to the start of each sublist
- maplist(cons(C), L3, L4),
- %% Convert to a list of terms
- maplist(term_to_list, L5, L4),
- %% Simplify the resulting polynomial
- simplify_polynomial_as_list(L5, L6),
- %% Return as a simplified polynomial
- list_to_polynomial(L6, S),
- !.
- %% Tests:
- %% ?- scale_polynomial(3*x^2, 2, S).
- %@ S = 6*x^2.
- %% cons(+C:atom, +L:List, -L2:List) is det
- %
- % Add an atom C to the head of a list L.
- %
- cons(C, L, [C | L]).
- %% Tests:
- %% ?- cons(C, L, L2).
- %@ L2 = [C|L].
- %% add_polynomial(+P1:polynomial,+P2:polynomial,-S:polynomial) is det
- %
- % S = P1 + P2.
- %
- add_polynomial(P1, P2, S) :-
- %% Convert both polynomials to lists
- polynomial_to_list(P1, L1),
- polynomial_to_list(P2, L2),
- %% Join them
- append(L1, L2, L3),
- %% Simplify the resulting polynomial
- simplify_polynomial_as_list(L3, L4),
- %% Convert back
- list_to_polynomial(L4, S),
- !.
- %% Tests:
- %% ?- add_polynomial(2, 2, S).
- %@ S = 4.
- %% ?- add_polynomial(x, x, S).
- %@ S = 2*x.
- %% ?- add_polynomial(2*x+5*z, 2*z+6*x, S).
- %@ S = 8*x+7*z.
|