/* 

  Horner's rule in Picat.

  From http://rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#K
  """
  A fast scheme for evaluating a polynomial such as:

    -19+7x-4x^2+6x^3\, 

  when

    x = 3 

   is to arrange the computation as follows:

    ((((0) x + 6) x + (-4)) x + 7) x + (-19); 

  And compute the result from the innermost brackets outwards as in this pseudocode:

     coefficients := [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order
     x := 3
     accumulator := 0
     for i in length(coefficients) downto 1 do
       # Assumes 1-based indexing for arrays
       accumulator := ( accumulator * x ) + coefficients[i]
     done
     # accumulator now has the answer

   Task Description

  Create a routine that takes a list of coefficients of a polynomial in order 
  of increasing powers of x; together with a value of x to compute its value at, 
  and return the value of the polynomial at that value using Horner's rule. 
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.

go =>
  horner([-19, 7, -4, 6], 3, V),
  println(V),
  
  horner2([-19, 7, -4, 6], 3, V2),
  println(V2),
  
  V3 = horner3([-19, 7, -4, 6], 3),
  println(V3),
  nl.


% Prolog style
horner([], _X, 0).
horner([H|T], X, V) :-
  horner(T, X, V1),
  V = V1 * X + H.

% Iterative version
horner2(Coeff, X, V) => 
  Acc = 0,
  foreach(I in Coeff.length..-1..1) 
     Acc := Acc*X + Coeff[I]
  end,
  V = Acc.

% Functional approach
h3(X,A,B) = A+B*X.
horner3(Coeff, X) = fold($h3(X),0,Coeff.reverse()).