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


 
bundle Default {
  class Test {
    function : Main(args : String[]) ~ Nil {
      a := [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0];
      Print(Diff(a, 1));
      Print(Diff(a, 2));
      Print(Diff(a, 9));
    }
 
    function : Print(a : Float[]) ~ Nil {
      if(a <> Nil) {
        '['->Print();
        each(i : a) {
          a[i]->Print(); ','->Print();
        };
        ']'->PrintLine();
      };
    }
 
    function : Diff(a : Float[], n : Int) ~ Float[] {
      if (n < 0) {
        return Nil;
       };
 
      for(i := 0; i < n & a->Size() > 0; i += 1;) {
        b := Float->New[a->Size() - 1];
        for(j := 0; j < b->Size(); j += 1;){
          b[j] := a[j+1] - a[j];
        };
        a := b;
      };
 
      return a;
    }
  }
}
 