Recurrence

Creates a mathematical sequence given the initial values and a recurrence function that computes the next value from the existing values. The sequence comes in the form of an infinite forward range. The type Recurrence itself is seldom used directly; most often, recurrences are obtained by calling the function recurrence.

When calling recurrence, the function that computes the next value is specified as a template argument, and the initial values in the recurrence are passed as regular arguments. For example, in a Fibonacci sequence, there are two initial values (and therefore a state size of 2) because computing the next Fibonacci value needs the past two values.

The signature of this function should be:

auto fun(R)(R state, size_t n)

where n will be the index of the current value, and state will be an opaque state vector that can be indexed with array-indexing notation state[i], where valid values of i range from (n - 1) to (n - State.length).

If the function is passed in string form, the state has name "a" and the zero-based index in the recurrence has name "n". The given string must return the desired value for a[n] given a[n - 1], a[n - 2], a[n - 3],..., a[n - stateSize]. The state size is dictated by the number of arguments passed to the call to recurrence. The Recurrence struct itself takes care of managing the recurrence's state and shifting it appropriately.

struct Recurrence (

alias fun

StateType

size_t stateSize

) {

template binaryFun(alias fun, string parm1Name = "a", string parm2Name = "b") via import std.functional : binaryFun;;

StateType[stateSize] _state;

size_t _n;

enum bool empty;

}

Examples

import std.algorithm.comparison : equal;

// The Fibonacci numbers, using function in string form:
// a[0] = 1, a[1] = 1, and compute a[n+1] = a[n-1] + a[n]
auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);
assert(fib.take(10).equal([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));

// The factorials, using function in lambda form:
auto fac = recurrence!((a,n) => a[n-1] * n)(1);
assert(take(fac, 10).equal([
    1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
]));

// The triangular numbers, using function in explicit form:
static size_t genTriangular(R)(R state, size_t n)
{
    return state[n-1] + n;
}
auto tri = recurrence!genTriangular(0);
assert(take(tri, 10).equal([0, 1, 3, 6, 10, 15, 21, 28, 36, 45]));

Recurrence

Examples

Meta

Source