Forward difference
Provide code that produces a list of numbers which is the n-th 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 less element as a result. The second-order forward difference of A will be 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.
You are encouraged to solve this task according to the task description, using any language you may know.
For a more formal description, see the related Mathworld article.
Ada
<lang ada>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;</lang> Output:
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] [54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] [-2921.0] Empty List [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]
ALGOL 68
<lang algol68>main:(
MODE LISTREAL = [1:0]REAL;
OP - = (LISTREAL a,b)LISTREAL: ( [UPB a]REAL out; FOR i TO UPB out DO out[i]:=a[i]-b[i] OD; out );
FORMAT real fmt=$zzz-d.d$;
FORMAT repeat fmt = $n(UPB s-1)(f(real fmt)",")f(real fmt)$;
FORMAT list fmt = $"("f(UPB s=1|real fmt|repeat fmt)")"$;
FLEX [1:0] REAL s := (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);
printf((list fmt,s,$";"l$)); TO UPB s-1 DO s := s[2:] - s[:UPB s-1]; printf((list fmt,s,$";"l$)) OD
)</lang> Output: <lang algol68>( 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0); ( -43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0); ( 54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0); ( -94.0, 62.0, -5.0, -4.0, -86.0, 173.0, -132.0); ( 156.0, -67.0, 1.0, -82.0, 259.0, -305.0); ( -223.0, 68.0, -83.0, 341.0, -564.0); ( 291.0, -151.0, 424.0, -905.0); ( -442.0, 575.0,-1329.0); ( 1017.0,-1904.0); (-2921.0);</lang>
APL
<lang apl> list ← 90 47 58 29 22 32 55 5 55 73
fd ← {⍺=0:⍵⋄(⍺-1)∇(1↓⍵)-(¯1↓⍵)}
1 fd list
¯43 11 ¯29 ¯7 10 23 ¯50 50 18
2 fd list
54 ¯40 22 17 13 ¯73 100 ¯32</lang>
AutoHotkey
contributed by Laszlo on the ahk forum <lang AutoHotkey>MsgBox % diff("2,3,4,3",1) MsgBox % diff("2,3,4,3",2) MsgBox % diff("2,3,4,3",3) MsgBox % diff("2,3,4,3",4)
diff(list,ord) { ; high order forward differences of a list
Loop %ord% {
L =
Loop Parse, list, `, %A_Space%%A_Tab%
If (A_Index=1)
p := A_LoopField
Else
L .= "," A_LoopField-p, p := A_LoopField
list := SubStr(L,2)
}
Return list
}</lang>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
void Fdiff(int *a, int na, int n) {
int i, j; int *b = malloc(sizeof(int)*na);
memcpy(b, a, sizeof(int)*na);
for(i=na-1; i >= (na - n); i--) {
for(j=1; j <= i; j++) {
b[j-1] = b[j] - b[j-1];
}
}
for(i=1; i <= (na-n); i++) printf("%d ", b[i-1]);
printf("\n");
free(b);
}</lang>
<lang c>int array[] = { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 };
int main() {
int i;
for(i=0; i < sizeof(array)/sizeof(int); i++) {
Fdiff(array, sizeof(array)/sizeof(int), i);
}
return EXIT_SUCCESS;
}</lang>
C++
This code uses a separate function to do a first-order forward difference, which is then called several times for calculating n-th order forward difference. No error checking is implemented. <lang cpp>#include <vector>
- include <iterator>
- include <algorithm>
// calculate first order forward difference // requires: // * InputIterator is an input iterator // * OutputIterator is an output iterator // * The value type of InputIterator is copy-constructible and assignable // * The value type of InputIterator supports operator - // * The result type of operator- is assignable to the value_type of OutputIterator // returns: The iterator following the output sequence template<typename InputIterator, typename OutputIterator>
OutputIterator forward_difference(InputIterator first, InputIterator last,
OutputIterator dest)
{
// special case: for empty sequence, do nothing if (first == last) return dest;
typedef typename std::iterator_traits<InputIterator>::value_type value_type;
value_type temp = *first++;
while (first != last)
{
value_type temp2 = *first++;
*dest++ = temp2 - temp;
temp = temp2;
}
return dest;
}
// calculate n-th order forward difference. // requires: // * InputIterator is an input iterator // * OutputIterator is an output iterator // * The value type of InputIterator is copy-constructible and assignable // * The value type of InputIterator supports operator - // * The result type of operator- is assignable to the value_type of InputIterator // * The result type of operator- is assignable to the value_type of OutputIterator // * order >= 0 // returns: The iterator following the output sequence template<typename InputIterator, typename OutputIterator>
OutputIterator nth_forward_difference(int order,
InputIterator first, InputIterator last,
OutputIterator dest)
{
// special case: If order == 0, just copy input to output if (order == 0) return std::copy(first, last, dest);
// second special case: If order == 1, just forward to the first-order function if (order == 1) return forward_difference(first, last, dest);
// intermediate results are stored in a vector typedef typename std::iterator_traits<InputIterator>::value_type value_type; std::vector<value_type> temp_storage;
// fill the vector with the result of the first order forward difference forward_difference(first, last, std::back_inserter(temp_storage));
// the next n-2 iterations work directly on the vector
typename std::vector<value_type>::iterator begin = temp_storage.begin(),
end = temp_storage.end();
for (int i = 1; i < order-1; ++i)
end = forward_difference(begin, end, begin);
// the final iteration writes directly to the output iterator return forward_difference(begin, end, dest);
}
// example usage code
- include <iostream>
int main() {
double array[10] = { 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0 };
// this stores the results in the vector dest std::vector<double> dest; nth_forward_difference(1, array, array+10, std::back_inserter(dest));
// outut dest std::copy(dest.begin(), dest.end(), std::ostream_iterator<double>(std::cout, " ")); std::cout << std::endl;
// however, the results can also be output as they are calculated nth_forward_difference(2, array, array+10, std::ostream_iterator<double>(std::cout, " ")); std::cout << std::endl;
nth_forward_difference(9, array, array+10, std::ostream_iterator<double>(std::cout, " ")); std::cout << std::endl;
nth_forward_difference(10, array, array+10, std::ostream_iterator<double>(std::cout, " ")); std::cout << std::endl;
nth_forward_difference(0, array, array+10, std::ostream_iterator<double>(std::cout, " ")); std::cout << std::endl;
// finally, the results can also be written into the original array // (which of course destroys the original content) double* end = nth_forward_difference(3, array, array+10, array);
for (double* p = array; p < end; ++p) std::cout << *p << " "; std::cout << std::endl;
return 0;
}</lang>
This gives the following output:
-43 11 -29 -7 10 23 -50 50 18 54 -40 22 17 13 -73 100 -32 -2921 90 47 58 29 22 32 55 5 55 73 -94 62 -5 -4 -86 173 -132
Note the empty line indicating the empty sequence for order 10.
D
<lang d>import std.stdio: writefln;
T[] fdiff(T)(T[] arr, int level) {
T[] result;
if (level < 0 || level >= arr.length)
return result;
result = arr.dup;
for (int i = 0; i < level; i++)
foreach (j, ref el; result[0 .. $-i-1])
el = result[j + 1] - el;
result.length = result.length - level;
return result;
}
void main() {
auto data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
for (int i = 0; i < data.length; i++)
writefln(fdiff(data, i));
}</lang> Sampe output:
D:\00MY\dmd>fdiff [90.5 47 58 29 22 32 55 5 55 73.5] [-43.5 11 -29 -7 10 23 -50 50 18.5] [54.5 -40 22 17 13 -73 100 -31.5] [-94.5 62 -5 -4 -86 173 -131.5] [156.5 -67 1 -82 259 -304.5] [-223.5 68 -83 341 -563.5] [291.5 -151 424 -904.5] [-442.5 575 -1328.5] [1017.5 -1903.5] [-2921] []
Similar to the Python version: <lang d>T[] difn(T)(T[] s, int n) {
static T[] dif(T[] s) {
T[] result;
foreach (i, x; s[1..$])
result ~= x - s[i];
return result;
}
return n ? difn(dif(s), n-1) : s;
}</lang>
Clojure
<lang lisp>(defn fwd-diff [nums order]
(nth (iterate #(map - (next %) %)) nums) order)</lang>
Common Lisp
<lang lisp>(defun forward-difference (list)
(mapcar #'- (rest list) list))
(defun nth-forward-difference (list n)
(setf list (copy-list list)) (loop repeat n do (map-into list #'- (rest list) list)) (subseq list 0 (- (length list) n)))</lang>
E
<lang e>pragma.enable("accumulator") /** Single step. */ def forwardDifference(seq :List) {
return accum [] for i in 0..(seq.size() - 2) {
_.with(seq[i + 1] - seq[i])
}
}
/** Iterative implementation of the goal. */ def nthForwardDifference1(var seq :List, n :(int >= 0)) {
for _ in 1..n { seq := forwardDifference(seq) }
return seq
}
/** Imperative implementation of the goal. */ def nthForwardDifference2(seq :List, n :(int >= 0)) {
def buf := seq.diverge()
def finalSize := seq.size() - n
for lim in (finalSize..!seq.size()).descending() {
for i in 0..!lim {
buf[i] := buf[i + 1] - buf[i]
}
}
return buf.run(0, finalSize)
}
? def sampleData := [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] > for n in 0..10 { > def r1 := nthForwardDifference1(sampleData, n) > require(r1 == nthForwardDifference2(sampleData, n)) > println(r1) > }</lang>
Factor
<lang factor>USING: kernel math math.vectors sequences ; IN: rosetacode
- 1-order ( seq -- seq' )
[ rest-slice ] keep v- ;
- n-order ( seq n -- seq' )
dup 0 <= [ drop ] [ [ 1-order ] times ] if ;
</lang>
( scratchpad ) { 90.5 47 58 29 22 32 55 5 55 73.5 } 4 n-order .
{ 156.5 -67 1 -82 259 -304.5 }
Fortran
<lang fortran>MODULE DIFFERENCE
IMPLICIT NONE
CONTAINS
SUBROUTINE Fdiff(a, n)
INTEGER, INTENT(IN) :: a(:), n
INTEGER :: b(SIZE(a))
INTEGER :: i, j, arraysize
b = a
arraysize = SIZE(b)
DO i = arraysize-1, arraysize-n, -1
DO j = 1, i
b(j) = b(j+1) - b(j)
END DO
END DO
WRITE (*,*) b(1:arraysize-n)
END SUBROUTINE Fdiff
END MODULE DIFFERENCE</lang>
<lang fortran>PROGRAM TEST
USE DIFFERENCE IMPLICIT NONE
INTEGER :: array(10) = (/ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 /) INTEGER :: i DO i = 1, 9 CALL Fdiff(array, i) END DO
END PROGRAM TEST</lang>
Output
-43 11 -29 -7 10 23 -50 50 18
54 -40 22 17 13 -73 100 -32
-94 62 -5 -4 -86 173 -132
156 -67 1 -82 259 -305
-223 68 -83 341 -564
291 -151 424 -905
-442 575 -1329
1017 -1904
-2921
F#
Straightforward recursive solution <lang fsharp>let rec ForwardDifference input n =
match n with
| _ when input = [] || n < 0 -> [] // If there's no more input, just return an empty list
| 0 -> input // If n is zero, we're done - return the input
| _ -> ForwardDifference // otherwise, recursively difference..
(input.Tail // All but the first element
|> Seq.zip input // tupled with itself
|> Seq.map (fun (a, b) -> b-a) // Subtract the i'th element from the (i+1)'th
|> Seq.toList) (n-1) // Make into a list and do an n-1 difference on it</lang>
Haskell
<lang haskell>forwardDifference xs = zipWith (-) (tail xs) xs
nthForwardDifference xs n = iterate forwardDifference xs !! n
> take 10 (iterate forwardDifference [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]) [[90,47,58,29,22,32,55,5,55,73],
[-43,11,-29,-7,10,23,-50,50,18], [54,-40,22,17,13,-73,100,-32], [-94,62,-5,-4,-86,173,-132], [156,-67,1,-82,259,-305], [-223,68,-83,341,-564], [291,-151,424,-905], [-442,575,-1329], [1017,-1904], [-2921]]</lang>
IDL
Standard IDL library function TS_diff(X,k,[/double]):
<lang idl>print,(x = randomu(seed,8)*100)
15.1473 58.0953 82.7465 16.8637 97.7182 59.7856 17.7699 74.9154
print,ts_diff(x,1)
-42.9479 -24.6513 65.8828 -80.8545 37.9326 42.0157 -57.1455 0.000000
print,ts_diff(x,2)
-18.2967 -90.5341 146.737 -118.787 -4.08316 99.1613 0.000000 0.000000
print,ts_diff(x,3)
72.2374 -237.271 265.524 -114.704 -103.244 0.000000 0.000000 0.000000</lang>
J
Of the many ways to code this in J, a particularly concise solution is: <lang j>fd=: 2&(-~/\)</lang>
Alternatively, to reduce the number of J primitives (rather than characters), use: <lang j>fd=: (}.-}:)^:</lang>
(which is also elegant, because the open-ended power conjunction reads like "to the power of anything").
For example: <lang j> list =: 90 47 58 29 22 32 55 5 55 73 NB. Some numbers
1 fd list
_43 11 _29 _7 10 23 _50 50 18
2 fd list
54 _40 22 17 13 _73 100 _32</lang>
J is array oriented, so you can even ask for more than one forward difference at a time (i.e. N can be a list, instead of a single number): <lang j> 1 2 3 fd list NB. First, second, and third forward differences (simultaneously) 43 _11 29 7 _10 _23 50 _50 _18 54 _40 22 17 13 _73 100 _32 0 94 _62 5 4 86 _173 132 0 0
a: fd list NB. All forward differences 90 47 58 29 22 32 55 5 55 73 43 _11 29 7 _10 _23 50 _50 _18 0 54 _40 22 17 13 _73 100 _32 0 0 94 _62 5 4 86 _173 132 0 0 0 156 _67 1 _82 259 _305 0 0 0 0 223 _68 83 _341 564 0 0 0 0 0 291 _151 424 _905 0 0 0 0 0 0 442 _575 1329 0 0 0 0 0 0 0
1017 _1904 0 0 0 0 0 0 0 0 2921 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0</lang>
Java
<lang java>import java.util.Arrays; public class FD {
public static void main(String args[]) {
double[] a = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73};
System.out.println(Arrays.toString(dif(a, 1)));
System.out.println(Arrays.toString(dif(a, 2)));
System.out.println(Arrays.toString(dif(a, 9)));
System.out.println(Arrays.toString(dif(a, 10))); //let's test
System.out.println(Arrays.toString(dif(a, 11)));
System.out.println(Arrays.toString(dif(a, -1)));
System.out.println(Arrays.toString(dif(a, 0)));
}
public static double[] dif(double[] a, int n) {
if (n < 0)
return null; // if the programmer was dumb
for (int i = 0; i < n && a.length > 0; i++) {
double[] b = new double[a.length - 1];
for (int j = 0; j < b.length; j++){
b[j] = a[j+1] - a[j];
}
a = b; //"recurse"
}
return a;
}
}</lang>
Output:
[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0] [54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0] [-2921.0] [] [] null [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]
Logo
<lang logo>to fwd.diff :l
if empty? :l [output []] if empty? bf :l [output []] output fput (first bf :l)-(first :l) fwd.diff bf :l
end to nth.fwd.diff :n :l
if :n = 0 [output :l] output nth.fwd.diff :n-1 fwd.diff :l
end
show nth.fwd.diff 9 [90 47 58 29 22 32 55 5 55 73] [-2921]</lang>
Lua
<lang lua>function dif(a, b, ...)
if(b) then return b-a, dif(b, ...) end
end function dift(t) return {dif(unpack(t))} end print(unpack(dift{1,3,6,10,15}))</lang>
Mathematica
Built-in function: <lang Mathematica>i={3,5,12,1,6,19,6,2,4,9}; Differences[i]</lang> gives back: <lang Mathematica>{2, 7, -11, 5, 13, -13, -4, 2, 5}</lang> The nth difference can be done as follows: <lang Mathematica>i={3,5,12,1,6,19,6,2,4,9}; Differences[i,n]</lang>
Nial
Define forward difference for order 1 <lang nial>fd is - [rest, front]</lang> forward difference of 4th order <lang nial>b := 90 47 58 29 22 32 55 5 55 73 4 fold fd b = 156 -67 1 -82 259 -305</lang>
OCaml
<lang ocaml>let rec forward_difference = function
a :: (b :: _ as xs) ->
b - a :: forward_difference xs
| _ ->
[]
let rec nth_forward_difference n xs =
if n = 0 then xs else nth_forward_difference (pred n) (forward_difference xs)</lang>
Output:
# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];; - : int list = [-2921]
Octave
<lang octave>% RECURSIVE function r = forwarddiff(a, n)
if ( n == 1 ) r = a(2:size(a,2)) - a(1:size(a,2)-1); else r = forwarddiff(a, 1); r = forwarddiff(r, n-1); endif
endfunction
% ITERATIVE function r = fdiff(a, n)
r = a; for i = 1:n r = r(2:size(r,2)) - r(1:size(r,2)-1); endfor
endfunction
% TEST v = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; disp(fdiff(v, 9)); disp(forwarddiff(v, 9);</lang>
Perl
<lang perl>sub dif {
my @s = @_;
map { $s[$_+1] - $s[$_] } 0 .. $#s-1
}
sub difn {
my ($n, @s) = @_; @s = dif @s foreach 1..$n; @s
}</lang>
Perl 6
<lang perl6>sub dif (@a) { map { $^x - $^y }, (@a[1 ..^ @a] Z @a) }
multi difn (@a, 0) { @a } multi difn (@a, $n) { difn dif(@a), $n - 1 }</lang>
PHP
<lang php><?php
function forwardDiff($anArray, $times = 1) {
if ($times <= 0) { return $anArray; }
for ($accumilation = array(), $i = 1, $j = count($anArray); $i < $j; ++$i) {
$accumilation[] = $anArray[$i] - $anArray[$i - 1];
}
if ($times === 1) { return $accumilation; }
return forwardDiff($accumilation, $times - 1);
}
class ForwardDiffExample extends PweExample {
function _should_run_empty_array_for_single_elem() {
$expected = array($this->rand()->int());
$this->spec(forwardDiff($expected))->shouldEqual(array());
}
function _should_give_diff_of_two_elem_as_single_elem() {
$twoNums = array($this->rand()->int(), $this->rand()->int());
$expected = array($twoNums[1] - $twoNums[0]);
$this->spec(forwardDiff($twoNums))->shouldEqual($expected);
}
function _should_compute_correct_forward_diff_for_longer_arrays() {
$diffInput = array(10, 2, 9, 6, 5);
$expected = array(-8, 7, -3, -1);
$this->spec(forwardDiff($diffInput))->shouldEqual($expected);
}
function _should_apply_more_than_once_if_specified() {
$diffInput = array(4, 6, 9, 3, 4);
$expectedAfter1 = array(2, 3, -6, 1);
$expectedAfter2 = array(1, -9, 7);
$this->spec(forwardDiff($diffInput, 1))->shouldEqual($expectedAfter1);
$this->spec(forwardDiff($diffInput, 2))->shouldEqual($expectedAfter2);
}
function _should_return_array_unaltered_if_no_times() {
$this->spec(forwardDiff($expected = array(1,2,3), 0))->shouldEqual($expected);
}
}</lang>
Pop11
<lang pop11>define forward_difference(l);
lvars res = [], prev, el;
if l = [] then
return([]);
endif;
front(l) -> prev;
for el in back(l) do
cons(el - prev, res) -> res;
el -> prev;
endfor;
rev(res);
enddefine;
define nth_difference(l, n);
lvars res = l, i;
for i from 1 to n do
forward_difference(res) -> res;
endfor;
res;
enddefine;</lang>
Python
<lang python>>>> dif = lambda s: [x-s[i] for i,x in enumerate(s[1:])] >>> # or, dif = lambda s: [x-y for x,y in zip(s[1:],s[:-1])] >>> difn = lambda s, n: difn(dif(s), n-1) if n else s
>>> s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] >>> difn(s, 0) [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] >>> difn(s, 1) [-43, 11, -29, -7, 10, 23, -50, 50, 18] >>> difn(s, 2) [54, -40, 22, 17, 13, -73, 100, -32]
>>> from pprint import pprint >>> pprint( [difn(s, i) for i in xrange(10)] ) [[90, 47, 58, 29, 22, 32, 55, 5, 55, 73],
[-43, 11, -29, -7, 10, 23, -50, 50, 18], [54, -40, 22, 17, 13, -73, 100, -32], [-94, 62, -5, -4, -86, 173, -132], [156, -67, 1, -82, 259, -305], [-223, 68, -83, 341, -564], [291, -151, 424, -905], [-442, 575, -1329], [1017, -1904], [-2921]]</lang>
R
<lang R>forwarddif <- function(a, n) {
if ( n == 1 )
a[2:length(a)] - a[1:length(a)-1]
else {
r <- forwarddif(a, 1)
forwarddif(r, n-1)
}
}
fdiff <- function(a, n) {
r <- a
for(i in 1:n) {
r <- r[2:length(r)] - r[1:length(r)-1]
}
r
}
v <- c(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)
print(forwarddif(v, 9)) print(fdiff(v, 9))</lang>
Ruby
<lang ruby>def dif(s)
s.enum_cons(2).collect { |x, y| y - x }
end
def difn(s, n)
n.times.inject(s) { |s, | dif(s) }
end</lang>
Scala
<lang scala>def fdiff(n:List[Int]) = n.tail.zip(n).map{case (x,y)=>x-y}
def fdiffn(i:Int,n:List[Int]):List[Int] = if (i==1) fdiff(n) else fdiffn(i-1,fdiff(n))</lang>
Example: <lang scala>val l=List(90,47,58,29,22,32,55,5,55,73) (1 to 9)foreach(x=>println(fdiffn(x,l)))</lang>
Output:
List(-43, 11, -29, -7, 10, 23, -50, 50, 18) List(54, -40, 22, 17, 13, -73, 100, -32) List(-94, 62, -5, -4, -86, 173, -132) List(156, -67, 1, -82, 259, -305) List(-223, 68, -83, 341, -564) List(291, -151, 424, -905) List(-442, 575, -1329) List(1017, -1904) List(-2921)
Scheme
<lang scheme>(define (forward-diff lst)
(if (or (null? lst) (null? (cdr lst)))
'()
(cons (- (cadr lst) (car lst))
(forward-diff (cdr lst)))))
(define (nth-forward-diff n xs)
(if (= n 0)
xs
(nth-forward-diff (- n 1)
(forward-diff xs))))</lang>
Output:
> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73)) (-2921)
Slate
<lang slate>s@(Sequence traits) forwardDifference [
s allButFirst with: s allButLast collect: [| :a :b | a - b]
].
s@(Sequence traits) forwardDifference "Without creating two intermediate throwaway Sequences." [| result |
result: s allButFirst. result doWithIndex: [| :nextValue :index | result at: index put: (result at: index) - (s at: index)]. result
].
s@(Sequence traits) forwardDifference: n [
(0 below: n) inject: s into: [| :seq :_ | seq forwardDifference]
].</lang> Usage: <lang slate>define: #data -> #(90 47 58 29 22 32 55 5 55 73). data keysDo: [| :index | inform: (data forwardDifference: index) printString].</lang>
Smalltalk
<lang smalltalk>Array extend [
difference [
^self allButFirst with: self allButLast collect: [ :a :b | a - b ]
]
nthOrderDifference: n [
^(1 to: n) inject: self into: [ :old :unused | old difference ]
]
]
s := #(90 47 58 29 22 32 55 5 55 73) 1 to: s size - 1 do: [ :i |
(s nthOrderDifference: i) printNl ]</lang>
Standard ML
<lang sml>fun forward_difference xs = ListPair.map op- (tl xs, xs)
fun nth_forward_difference n xs =
if n = 0 then xs else nth_forward_difference (n-1) (forward_difference xs)</lang>
Output:
- nth_forward_difference 9 [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]; val it = [~2921] : int list
Tcl
<lang tcl>proc do_fwd_diff {list} {
set previous [lindex $list 0]
set new [list]
foreach current [lrange $list 1 end] {
lappend new [expr {$current - $previous}]
set previous $current
}
return $new
}
proc fwd_diff {list order} {
while {$order >= 1} {
set list [do_fwd_diff $list]
incr order -1
}
return $list
}
set a {90.5 47 58 29 22 32 55 5 55 73.5}
for {set order 0} {$order <= 10} {incr order} {
puts [format "%d\t%s" $order [fwd_diff $a $order]]
}</lang>
0 90.5 47 58 29 22 32 55 5 55 73.5 1 -43.5 11 -29 -7 10 23 -50 50 18.5 2 54.5 -40 22 17 13 -73 100 -31.5 3 -94.5 62 -5 -4 -86 173 -131.5 4 156.5 -67 1 -82 259 -304.5 5 -223.5 68 -83 341 -563.5 6 291.5 -151 424 -904.5 7 -442.5 575 -1328.5 8 1017.5 -1903.5 9 -2921.0 10
Ursala
This function doesn't need to be defined because it's in a library already, but it could be defined like this. <lang Ursala>#import std
- import nat
- import flo
nth_diff "n" = rep"n" minus*typ</lang> test program: <lang Ursala>test_data = <90.,47.,58.,29.,22.,32.,55.,5.,55.,73.>
- show+
examples =
printf/*=*' %0.0f' <
nth_diff6 test_data, nth_diff7 test_data></lang>
output:
291 -151 424 -905 -442 575 -1329