Forward difference

From Rosetta Code

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 B_n = A_n+1 - A_n. 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.

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

Contents 1 Ada 2 ALGOL 68 3 APL 4 AutoHotkey 5 C 6 C++ 7 D 8 Clojure 9 Common Lisp 10 E 11 Factor 12 Fortran 13 F# 14 Haskell 15 IDL 16 J 17 Java 18 Logo 19 Lua 20 Mathematica 21 Nial 22 OCaml 23 Octave 24 Perl 25 Perl 6 26 PHP 27 Pop11 28 Python 29 R 30 Ruby 31 Scala 32 Scheme 33 Slate 34 Smalltalk 35 Standard ML 36 Tcl 37 Ursala

[edit] 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;

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]

[edit] ALGOL 68

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
)

Output:

(   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);

[edit] APL

Works with: Dyalog APLTranslation of: J

      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

[edit] AutoHotkey

contributed by Laszlo on the ahk forum

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
}

[edit] C

Translation of: Fortran

#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);
}

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;
}

[edit] C++

Works with: g++ version 4.1.2 20061115 (prerelease) (SUSE Linux)

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.

#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;
}

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.

[edit] 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));
}

Sampe output:

[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:

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;
}

[edit] Clojure

(defn fwd-diff [nums order]
  (nth (iterate #(map - (next %) %)) nums) order)

[edit] Common 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)))

[edit] 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)
> }

[edit] 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 ;
 

 ( scratchpad ) { 90.5 47 58 29 22 32 55 5 55 73.5 } 4 n-order .
 { 156.5 -67 1 -82 259 -304.5 }

[edit] Fortran

Works with: Fortran version 90 and later

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

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

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

[edit] F#

Straightforward recursive solution

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

[edit] 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]]

[edit] IDL

Standard IDL library function TS_diff(X,k,[/double]):

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

[edit] J

Of the many ways to code this in J, a particularly concise solution is:

fd=: 2&(-~/\)

Alternatively, to reduce the number of J primitives (rather than characters), use:

fd=: (}.-}:)^:

(which is also elegant, because the open-ended power conjunction reads like "to the power of anything").

For example:

   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

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

   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

[edit] Java

Works with: Java version 1.5+

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;
    }
}

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]

[edit] 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]

[edit] 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}))

[edit] Mathematica

Built-in function:

i={3,5,12,1,6,19,6,2,4,9};
Differences[i]

gives back:

{2, 7, -11, 5, 13, -13, -4, 2, 5}

The n^th difference can be done as follows:

i={3,5,12,1,6,19,6,2,4,9};
Differences[i,n]

[edit] Nial

Define forward difference for order 1

fd is - [rest, front]

forward difference of 4th order

b := 90 47 58 29 22 32 55 5 55 73 
4 fold fd b
= 156 -67 1 -82 259 -305

[edit] 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)

Output:

# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];;
- : int list = [-2921]

[edit] 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);

[edit] Perl

sub dif {
  my @s = @_;
  map { $s[$_+1] - $s[$_] } 0 .. $#s-1
}
 
sub difn {
  my ($n, @s) = @_;
  @s = dif @s foreach 1..$n;
  @s
}

[edit] Perl 6

Works with: Rakudo version #22 "Thousand Oaks"

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 }

[edit] 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);
  }
 
}

[edit] 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;

[edit] 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]]

[edit] 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))

[edit] 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

[edit] 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))

Example:

val l=List(90,47,58,29,22,32,55,5,55,73)
(1 to 9)foreach(x=>println(fdiffn(x,l)))

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)

[edit] 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))))

Output:

> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73))
(-2921)

[edit] 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]
].

Usage:

define: #data -> #(90 47 58 29 22 32 55 5 55 73).
data keysDo: [| :index | inform: (data forwardDifference: index) printString].

[edit] Smalltalk

Works with: GNU 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 ]

[edit] Standard ML

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)

Output:

- nth_forward_difference 9 [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
val it = [~2921] : int list

[edit] 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]]
}

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	

[edit] Ursala

This function doesn't need to be defined because it's in a library already, but it could be defined like this.

#import std
#import nat
#import flo
 
nth_diff "n" = rep"n" minus*typ

test program:

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>

output:

 291 -151 424 -905
 -442 575 -1329