Task

Provide code that produces a list of numbers which is the   nth  order forward difference, given a non-negative integer (specifying the order) and a list of numbers.



The first-order forward difference of a list of numbers   A   is a new list   B,   where   Bn = An+1 - An.

List   B   should have one fewer element as a result.

The second-order forward difference of   A   will be:

tdefmodule Diff do
	def forward(arr,i\\1) do
		forward(arr,[],i)
	end

	def forward([_|[]],diffs,i) do
		if i == 1 do
			IO.inspect diffs
		else 
			forward(diffs,[],i-1)
		end
	end

	def forward([val1|[val2|vals]],diffs,i) do
		forward([val2|vals],diffs++[val2-val1],i) 
	end
end 

The same as the first-order forward difference of   B.

That new list will have two fewer elements than   A   and one less than   B.

The goal of this task is to repeat this process up to the desired order.

For a more formal description, see the related   Mathworld article.



Algorithmic options

 Iterate through all previous forward differences and re-calculate a new array each time.
 Use this formula (from Wikipedia):


 




Δ

n


[
f
]
(
x
)
=

∑

k
=
0


n





(


n
k


)



(
−
1

)

n
−
k


f
(
x
+
k
)


{\displaystyle \Delta ^{n}[f](x)=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}f(x+k)}




 (Pascal's Triangle   may be useful for this option.)


with Ada.Text_Io;
with Ada.Float_Text_Io; use Ada.Float_Text_Io;
with Ada.containers.Vectors;
 
procedure Forward_Difference is
   package Flt_Vect is new Ada.Containers.Vectors(Positive, Float);
   use Flt_Vect;
   procedure Print(Item : Vector) is
   begin
      if not Item.Is_Empty then
         Ada.Text_IO.Put('[');
         for I in 1..Item.Length loop
            Put(Item => Item.Element(Positive(I)), Fore => 1, Aft => 1, Exp => 0);
             if Positive(I) < Positive(Item.Length) then
               Ada.Text_Io.Put(", ");
            end if;
         end loop;
         Ada.Text_Io.Put_line("]");
      else
         Ada.Text_IO.Put_Line("Empty List");
      end if;
 
   end Print;
 
  function Diff(Item : Vector; Num_Passes : Natural) return Vector is
      A : Vector := Item;
      B : Vector := Empty_Vector;
   begin
      if not A.Is_Empty then
         for I in 1..Num_Passes loop
            for I in 1..Natural(A.Length) - 1 loop
                  B.Append(A.Element(I + 1) - A.Element(I));
            end loop;
            Move(Target => A, Source => B);
         end loop;
      end if;
      return A;
   end Diff;
   Values : array(1..10) of Float := (90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0);
   A : Vector;
begin
   for I in Values'range loop
      A.Append(Values(I)); -- Fill the vector
   end loop;
   Print(Diff(A, 1));
   Print(Diff(A, 2));
   Print(Diff(A, 9));
   Print(Diff(A, 10));
   print(Diff(A, 0));
end Forward_Difference;