Comment #0 by bearophile_hugs — 2013-05-07T17:38:31Z
I suggest to add to Phobos the inits() and tails() random-access ranges similar to the Haskell functions:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v:inits
This is a bare-bones forward-range implementation, with an usage example, a inefficient function that finds the maximum subsequence:
import std.stdio, std.algorithm, std.range, std.typecons;
mixin template InitsTails(T) {
T[] data;
size_t pos;
@property bool empty() { return pos > data.length; }
void popFront() { pos++; }
}
struct Inits(T) {
mixin InitsTails!T;
@property T[] front() { return data[0 .. pos]; }
}
auto inits(T)(T[] seq) { return seq.Inits!T; }
struct Tails(T) {
mixin InitsTails!T;
@property T[] front() { return data[pos .. $]; }
}
auto tails(T)(T[] seq) { return seq.Tails!T; }
auto maxSubseq(T)(T[] seq) {
return seq
.tails
.map!inits
.join
.map!q{ tuple(reduce!q{a + b}(0, a), a) }
.reduce!max[1];
}
void main() {
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1].maxSubseq.writeln;
[-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1].maxSubseq.writeln;
}
Using the key function for the max() function as proposed in Issue 4705 the function becomes quite short:
auto maxSubseq(T)(T[] seq) {
return seq.tails.map!inits.join.reduce!(max!q{ a.sum });
}
Using maxs:
auto maxSubseq(T)(T[] seq) {
return seq.tails.map!inits.join.maxs!q{ a.sum };
}
Comment #1 by bearophile_hugs — 2013-10-16T15:58:15Z
Another usage example:
sequence!q{n}.inits.map!sum.take(20).writeln;
Should generate the the triangle number sequence (http://oeis.org/A000217 ), with an extra leading zero:
[0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171]
Comment #2 by robert.schadek — 2024-12-01T16:17:28Z