www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - transversal sum

reply "Jack Applegame" <japplegame gmail.com> writes:
I have rectangular forward range of forward ranges (not arrays):
[
   [a11, a12, ... a1N],
   [a21, a22, ... a2N],
   ...
   [aM1, aM2, ... aMN]
]

I need lazy forward range:
[
  a11 + a21 + ... aM1,
  a12 + a22 + ... aM2,
  ...
  a1N + a2N + ... aMN
]
Range of sum elements of every columns;

M, N - runtime values;

Is there a way to do this using only Phobos algorithms and range 
functions?
Nov 06 2014
next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame 
wrote:
 I have rectangular forward range of forward ranges (not arrays):
 [
   [a11, a12, ... a1N],
   [a21, a22, ... a2N],
   ...
   [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
  a11 + a21 + ... aM1,
  a12 + a22 + ... aM2,
  ...
  a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and 
 range functions?
Untested: import std.algorithm: map, sum; auto rangeOfSums = rectangularRange.map!(r => r.sum);
Nov 06 2014
next sibling parent reply Justin Whear <justin economicmodeling.com> writes:
On Thu, 06 Nov 2014 16:57:48 +0000, Marc Schütz wrote:

 On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame wrote:
 I have rectangular forward range of forward ranges (not arrays):
 [
   [a11, a12, ... a1N],
   [a21, a22, ... a2N],
   ...
   [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
  a11 + a21 + ... aM1,
  a12 + a22 + ... aM2,
  ...
  a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and range
 functions?
Untested: import std.algorithm: map, sum; auto rangeOfSums = rectangularRange.map!(r => r.sum);
This would sum along the wrong dimension. I think the correct solution will make use of std.range.frontTraversal, but it will be a bit more complex due to needing to sum every column. std.range.traversal would make it easy, but it requires random access.
Nov 06 2014
next sibling parent Justin Whear <justin economicmodeling.com> writes:
On Thu, 06 Nov 2014 17:08:23 +0000, Justin Whear wrote:

 I think the correct solution
 will make use of std.range.frontTraversal, but it will be a bit more
 complex due to needing to sum every column.  std.range.traversal would
 make it easy, but it requires random access.
That should be std.range.frontTransversal and transversal.
Nov 06 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 6 November 2014 at 17:08:23 UTC, Justin Whear wrote:
 This would sum along the wrong dimension.  I think the correct 
 solution
 will
 make use of std.range.frontTraversal, but it will be a bit more 
 complex
 due to
 needing to sum every column.  std.range.traversal would make it 
 easy, but
 it
 requires random access.
Yeah, I posted to soon. Was surprised that the solution would be so easy :-P We'd need something taking and returning a RoR that "mirrors" them diagonally. Then we could simply apply `map!(r => r.sum)` on the result.
Nov 06 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Marc Schütz:

 We'd need something taking and returning a RoR that "mirrors" 
 them diagonally. Then we could simply apply `map!(r => r.sum)` 
 on the result.
A simple solution is to create a row of values, and then sum them correctly while you scan the rows. Bye, bearophile
Nov 06 2014
parent reply Artur Skawina via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On 11/06/14 18:32, bearophile via Digitalmars-d-learn wrote:
 Marc Schütz:
 
 We'd need something taking and returning a RoR that "mirrors" them diagonally.
Then we could simply apply `map!(r => r.sum)` on the result.
A simple solution is to create a row of values, and then sum them correctly while you scan the rows.
The simplest solution is probably something like: auto transversal_sum(FR)(FR rr) { static struct TS { FR rr; bool empty() property const { return rr.front.empty; } auto front() property { import std.algorithm; return reduce!((a, b)=>a+b.front)(rr.front.front.init, rr); } void popFront() { foreach (ref r; rr) r.popFront(); } } return TS(rr); } but I think OP wanted a ready-made phobos solution, w/o all the range boilerplate... artur
Nov 06 2014
parent "Jack Applegame" <japplegame gmail.com> writes:
 void popFront() { foreach (ref r; rr) r.popFront(); }
I think it should be void popFront() { foreach (ref r; rr.save) r.popFront(); }
 but I think OP wanted a ready-made phobos solution, w/o all the
 range boilerplate...
exactly.
Nov 06 2014
prev sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 6 November 2014 at 16:57:50 UTC, Marc Schütz wrote:
 On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame 
 wrote:
 I have rectangular forward range of forward ranges (not 
 arrays):
 [
  [a11, a12, ... a1N],
  [a21, a22, ... a2N],
  ...
  [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
 a11 + a21 + ... aM1,
 a12 + a22 + ... aM2,
 ...
 a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and 
 range functions?
Untested: import std.algorithm: map, sum; auto rangeOfSums = rectangularRange.map!(r => r.sum);
Sorry, I see you want columns... I thought about std.range.frontTransversal, but it only returns a range of values, not a range of ranges. That's... unhelpful :-(
Nov 06 2014
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame 
wrote:
 I have rectangular forward range of forward ranges (not arrays):
 [
   [a11, a12, ... a1N],
   [a21, a22, ... a2N],
   ...
   [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
  a11 + a21 + ... aM1,
  a12 + a22 + ... aM2,
  ...
  a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and 
 range functions?
Can I get random access in one or both dimensions?
Nov 06 2014
parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 6 November 2014 at 22:02:09 UTC, John Colvin wrote:
 On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame 
 wrote:
 I have rectangular forward range of forward ranges (not 
 arrays):
 [
  [a11, a12, ... a1N],
  [a21, a22, ... a2N],
  ...
  [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
 a11 + a21 + ... aM1,
 a12 + a22 + ... aM2,
 ...
 a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and 
 range functions?
Can I get random access in one or both dimensions?
with random access along N: iota(N).map!((i) => ror.transversal(i).sum())
Nov 06 2014
prev sibling next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame 
wrote:
 I have rectangular forward range of forward ranges (not arrays):
 [
   [a11, a12, ... a1N],
   [a21, a22, ... a2N],
   ...
   [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
  a11 + a21 + ... aM1,
  a12 + a22 + ... aM2,
  ...
  a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and 
 range functions?
nasty inefficient solution, but might be ok if your ranges have cheap popFront: import std.algorithm, std.range, std.stdio, std.array; void main() { auto M = 3; auto N = 10; //generate a RangeOfRanges for testing auto ror = iota(1, M+1) .map!(l => iota(N) .map!(e => e * l^^2)); auto rorFlat = ror.joiner; iota(N) .map!(i => rorFlat.save.drop(i).stride(N)) .map!sum.writeln; }
Nov 06 2014
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 6 November 2014 at 15:53:27 UTC, Jack Applegame 
wrote:
 I have rectangular forward range of forward ranges (not arrays):
 [
   [a11, a12, ... a1N],
   [a21, a22, ... a2N],
   ...
   [aM1, aM2, ... aMN]
 ]

 I need lazy forward range:
 [
  a11 + a21 + ... aM1,
  a12 + a22 + ... aM2,
  ...
  a1N + a2N + ... aMN
 ]
 Range of sum elements of every columns;

 M, N - runtime values;

 Is there a way to do this using only Phobos algorithms and 
 range functions?
this should be a textbook case for std.range.transposed, but I can't seem to get it to work.
Nov 06 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 6 November 2014 at 22:40:58 UTC, John Colvin wrote:
 this should be a textbook case for std.range.transposed, but I 
 can't seem to get it to work.
Ah, I didn't know this existed. Apparently it's not yet released, that's why it's not in the official documentation. With DMD and Phobos from git: void main(string[] args) { import std.stdio: writeln; import std.range: transposed; import std.algorithm: map, sum; int[][] input = new int[][2]; input[0] = [1, 2, 3, 4]; input[1] = [5, 6, 7, 8]; writeln(input); auto sums = input .transposed .map!(a => a.sum); writeln(sums); } Output: [[1, 2, 3, 4], [5, 6, 7, 8]] [6, 8, 10, 12]
Nov 07 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Marc Schütz:

         int[][] input = new int[][2];
         input[0] = [1, 2, 3, 4];
         input[1] = [5, 6, 7, 8];
         writeln(input);

         auto sums = input
                 .transposed
                 .map!(a => a.sum);
         writeln(sums);
     }

 Output:

     [[1, 2, 3, 4], [5, 6, 7, 8]]
     [6, 8, 10, 12]
Jack specified:
 I have rectangular forward range of forward ranges (not arrays):
You "input" range is not just a Forward Range. And by the way, your array literal can be written more simply like this: int[][2] input = [[1, 2, 3, 4], [5, 6, 7, 8]]; Bye, bearophile
Nov 07 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Marc Schütz:

         auto sums = input
                 .transposed
                 .map!(a => a.sum);
And that part is better written: .map!sum; I also suggest to align the leading dot to the precedent line: auto sums = input .transposed .map!(a => a.sum); Bye, bearophile
Nov 07 2014
prev sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 7 November 2014 at 10:58:58 UTC, Marc Schütz wrote:
 On Thursday, 6 November 2014 at 22:40:58 UTC, John Colvin wrote:
 this should be a textbook case for std.range.transposed, but I 
 can't seem to get it to work.
Ah, I didn't know this existed. Apparently it's not yet released, that's why it's not in the official documentation. With DMD and Phobos from git: void main(string[] args) { import std.stdio: writeln; import std.range: transposed; import std.algorithm: map, sum; int[][] input = new int[][2]; input[0] = [1, 2, 3, 4]; input[1] = [5, 6, 7, 8]; writeln(input); auto sums = input .transposed .map!(a => a.sum); writeln(sums); } Output: [[1, 2, 3, 4], [5, 6, 7, 8]] [6, 8, 10, 12]
http://dlang.org/phobos-prerelease/std_range.html#.transposed yeah it works find for arrays, but it needs assignable elements.
Nov 07 2014