std.range.Recurrence/recurrence
- multiple declarations
Function 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
.
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.
Example
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]));
Struct 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
.
struct Recurrence(alias fun, StateType, ulong stateSize)
;
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
.
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.
Example
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]));
Authors
Andrei Alexandrescu, David Simcha, Jonathan M Davis, and Jack Stouffer. Credit for some of the ideas in building this module goes to Leonardo Maffi.