## digitalmars.D.learn - Using reduce() with tuples created by zip()

• Craig Dillabaugh (32/32) Oct 31 2013 I am trying to calculate the Euclidean Distance between two
• Philippe Sigaud (21/53) Oct 31 2013 I think reduce takes two arguments: the growing seed and the current fro...
• Craig Dillabaugh (10/36) Oct 31 2013 Yep. The (e[1]-e[0])*(e[1]-e[0]) bit was, I supposed was
• Philippe Sigaud (36/39) Nov 01 2013 reduce takes a range and eagerly (that is, not lazily) builds a value fr...
• bearophile (5/9) Nov 01 2013 It's already in Bugzilla:
• Craig Dillabaugh (11/71) Nov 01 2013 This is really where my problem arose. I understood everything up
• Philippe Sigaud (2/12) Nov 01 2013 The problem is not tuple, it's that reduce needs a binary function to wo...
• Craig Dillabaugh (5/27) Nov 01 2013 Yes, that is more or less what I was trying to say. I was
• Philippe Sigaud (7/7) Nov 01 2013 What I'm trying to explain is that reduce takes two arguments: the growi...
• Craig Dillabaugh (5/14) Nov 02 2013 OK, NOW I understand what you were trying to point out. The
• bearophile (20/23) Oct 31 2013 import std.stdio, std.algorithm, std.range, std.math,
• bearophile (9/24) Oct 31 2013 In D functions are written in camelCase like euclidDistance,
"Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
```I am trying to calculate the Euclidean Distance between two
points. I currently have the following function (that doesn't
compile):

double euclid_dist( double[] pt1, double[] pt2 ) {
assert( pt1.length == pt2.length );

return sqrt(
zip(pt1, pt2).reduce!(function(e) { return
(e[1]-e[0])*(e[1]-e[0]); })(0.0)
);
}

Hopefully it is clear what I am trying to do.  I want zip to
create a range that is a tuple of the point's coordinate pairs,
and then use reduce to sum the squared differences.  I get the
following error but can't figure out how to fix my syntax:

euclid.d(13): Error: template
euclid.euclid_dist.reduce!(__funcliteral2).reduce does not match
any function template declaration. Candidates are:
/usr/include/dmd/phobos/std/algorithm.d(688):
euclid.euclid_dist.reduce!(__funcliteral2).reduce(Args...)(Args
args) if (Args.length > 0 && Args.length <= 2 &&
isIterable!(Args[__dollar - 1]))
euclid.d(13): Error: template
euclid.euclid_dist.reduce!(__funcliteral2).reduce(Args...)(Args
args) if (Args.length > 0 && Args.length <= 2 &&
isIterable!(Args[__dollar - 1])) cannot deduce template function
from argument types !()(Zip!(double[], double[]), double)
Failed: 'dmd' '-v' '-o-' 'euclid.d' '-I.'

I know I could use a simple foreach loop with my zip command, or
even std.numeric.euclidean( ... ), but I am trying to be cute
here!

Cheers,
Craig
```
Oct 31 2013
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```I think reduce takes two arguments: the growing seed and the current front.
You're trying to get (a[0]-b[0])^^2 + (a[1]-b[1])^^2 + ..., right?

Try this:

module euclid;

import std.stdio;

double euclid_dist( double[] pt1, double[] pt2 ) {
assert( pt1.length == pt2.length );
import std.algorithm;
import std.math;
import std.range;

return sqrt(0.0.reduce!( (sum,pair) => sum + (pair[0]-pair[1])^^2
)(zip(pt1, pt2)));
}

void main()
{
double[] arr1 = [0.0, 1.0, 0.1];
double[] arr2 = [1.0, -1.0, 0.0];
writeln(euclid_dist(arr1,arr2));
}

On Thu, Oct 31, 2013 at 8:12 PM, Craig Dillabaugh <
cdillaba cg.scs.carleton.ca> wrote:

I am trying to calculate the Euclidean Distance between two
points. I currently have the following function (that doesn't
compile):

double euclid_dist( double[] pt1, double[] pt2 ) {
assert( pt1.length == pt2.length );

return sqrt(
zip(pt1, pt2).reduce!(function(e) { return
(e[1]-e[0])*(e[1]-e[0]); })(0.0)
);
}

Hopefully it is clear what I am trying to do.  I want zip to
create a range that is a tuple of the point's coordinate pairs,
and then use reduce to sum the squared differences.  I get the
following error but can't figure out how to fix my syntax:

euclid.d(13): Error: template
euclid.euclid_dist.reduce!(__**funcliteral2).reduce does not match
any function template declaration. Candidates are:
/usr/include/dmd/phobos/std/**algorithm.d(688):
euclid.euclid_dist.reduce!(__**funcliteral2).reduce(Args...)(**Args
args) if (Args.length > 0 && Args.length <= 2 &&
isIterable!(Args[__dollar - 1]))
euclid.d(13): Error: template
euclid.euclid_dist.reduce!(__**funcliteral2).reduce(Args...)(**Args
args) if (Args.length > 0 && Args.length <= 2 &&
isIterable!(Args[__dollar - 1])) cannot deduce template function
from argument types !()(Zip!(double[], double[]), double)
Failed: 'dmd' '-v' '-o-' 'euclid.d' '-I.'

I know I could use a simple foreach loop with my zip command, or
even std.numeric.euclidean( ... ), but I am trying to be cute
here!

Cheers,
Craig

```
Oct 31 2013
"Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
```On Thursday, 31 October 2013 at 19:23:56 UTC, Philippe Sigaud
wrote:
I think reduce takes two arguments: the growing seed and the
current front.
You're trying to get (a[0]-b[0])^^2 + (a[1]-b[1])^^2 + ...,
right?

Yep. The (e[1]-e[0])*(e[1]-e[0]) bit was, I supposed was
effectively
calculating (a[0]-b[0])^^2 and so on.  I forgot about the ^^2 in
D.

Try this:

module euclid;

import std.stdio;

double euclid_dist( double[] pt1, double[] pt2 ) {
assert( pt1.length == pt2.length );
import std.algorithm;
import std.math;
import std.range;

return sqrt(0.0.reduce!( (sum,pair) => sum +
(pair[0]-pair[1])^^2
)(zip(pt1, pt2)));
}

void main()
{
double[] arr1 = [0.0, 1.0, 0.1];
double[] arr2 = [1.0, -1.0, 0.0];
writeln(euclid_dist(arr1,arr2));
}

On Thu, Oct 31, 2013 at 8:12 PM, Craig Dillabaugh <
cdillaba cg.scs.carleton.ca> wrote:

clip
Cheers,
Craig

Thanks, I will try both your, and Bearophile's ideas and see if I
can figure out how they work.
Craig
```
Oct 31 2013
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```On Thu, Oct 31, 2013 at 8:59 PM, Craig Dillabaugh <
cdillaba cg.scs.carleton.ca> wrote:

Thanks, I will try both your, and Bearophile's ideas and see if I
can figure out how they work.

reduce takes a range and eagerly (that is, not lazily) builds a value from
it. In your case, it builds the squared distance between two points.  The
returned value can be anything: a numerical value, but also another range,
a complex object,  an so on. As long as it can be built increasingly,
you're good.

Given a range [a,b,c,..., z] and a binary function f,
reduce!(f)([a,b,c,...]) calculates f(a,b), then f(f(a,b), c), up to f(...
f( f( f(a,b),c), d), ...,z).

The only question is whether you give it a seed value, or if it takes the
first range element as seed  (f(seed, a), f(f(seed,a),b) and son on).

Note the only thing you get is the final result, not the internal f(f(...'s
applications.

If you want a sum:

reduce!( (result,elem) => result + elem )(range)

or

reduce!( (result,elem) => result + elem )(range, 0)

Sum of squares:

reduce!( (result, elem) => result + elem^^2 )(range, 0)

two elements is done with [0] or [1]. So:

reduce!( (result, elem) => result + (elem[0]-elem[1])^^2 )(zippedRange, 0)

Of course, it would be easy to write a small n-range reduce helper
function, that takes n ranges and reduces them in parallel:

reduce!( (result, a, b) => result + (a-b)^^2 )(rangeA, rangeB, 0)

Note that reduce is a versatile function: you can duplicate filter and map
functionalities with it. The only thing to remember is that, compared to
other iteration algorithm/ranges, it's eager. Don't use it on an infinite
range!

We could also have a slightly different version that lazily produces the
intermediate results as a range. IIRC, it's called 'scan' in Haskell. It's
sometimes interesting to have it: you can interrupt the ongoing calculation
when the result is 'good enough', not waiting for the entire input range to
be consumed.
```
Nov 01 2013
"bearophile" <bearophileHUGS lycos.com> writes:
```Philippe Sigaud:

We could also have a slightly different version that lazily
produces the
intermediate results as a range. IIRC, it's called 'scan' in

http://d.puremagic.com/issues/show_bug.cgi?id=11084

Bye,
bearophile
```
Nov 01 2013
"Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
```On Friday, 1 November 2013 at 09:31:41 UTC, Philippe Sigaud wrote:
On Thu, Oct 31, 2013 at 8:59 PM, Craig Dillabaugh <
cdillaba cg.scs.carleton.ca> wrote:

Thanks, I will try both your, and Bearophile's ideas and see
if I
can figure out how they work.

reduce takes a range and eagerly (that is, not lazily) builds a
value from
it. In your case, it builds the squared distance between two
points.  The
returned value can be anything: a numerical value, but also
another range,
a complex object,  an so on. As long as it can be built
increasingly,
you're good.

Given a range [a,b,c,..., z] and a binary function f,
reduce!(f)([a,b,c,...]) calculates f(a,b), then f(f(a,b), c),
up to f(...
f( f( f(a,b),c), d), ...,z).

The only question is whether you give it a seed value, or if it
takes the
first range element as seed  (f(seed, a), f(f(seed,a),b) and
son on).

Note the only thing you get is the final result, not the
internal f(f(...'s
applications.

If you want a sum:

reduce!( (result,elem) => result + elem )(range)

or

reduce!( (result,elem) => result + elem )(range, 0)

Sum of squares:

reduce!( (result, elem) => result + elem^^2 )(range, 0)

In your case, the basic element is a tuple, coming from zip.
two elements is done with [0] or [1]. So:

reduce!( (result, elem) => result + (elem[0]-elem[1])^^2
)(zippedRange, 0)

This is really where my problem arose. I understood everything up
to here, but I sort of had this idea, "hey zip returns a tuple so
that somehow the compiler
was going to figure out for me that function(e) has two values"
and is thus
a binary function so this should work (the 0.0 on the end was my
start value):

reduce!(function(e) { return (e[1]-e[0])*(e[1]-e[0]); })(0.0)

However, of course the compiler see's the tuple as just one value
- which is where I made my mistake.

Of course, it would be easy to write a small n-range reduce
helper
function, that takes n ranges and reduces them in parallel:

reduce!( (result, a, b) => result + (a-b)^^2 )(rangeA, rangeB,
0)

Note that reduce is a versatile function: you can duplicate
filter and map
functionalities with it. The only thing to remember is that,
compared to
other iteration algorithm/ranges, it's eager. Don't use it on
an infinite
range!

We could also have a slightly different version that lazily
produces the
intermediate results as a range. IIRC, it's called 'scan' in
sometimes interesting to have it: you can interrupt the ongoing
calculation
when the result is 'good enough', not waiting for the entire
input range to
be consumed.

```
Nov 01 2013
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```reduce!( (result, elem) => result + (elem[0]-elem[1])^^2 )(zippedRange, 0)

This is really where my problem arose. I understood everything up
to here, but I sort of had this idea, "hey zip returns a tuple so
that somehow the compiler
was going to figure out for me that function(e) has two values"
and is thus
a binary function so this should work (the 0.0 on the end was my
start value):

reduce!(function(e) { return (e[1]-e[0])*(e[1]-e[0]); })(0.0)

However, of course the compiler see's the tuple as just one value
- which is where I made my mistake.

The problem is not tuple, it's that reduce needs a binary function to work.
```
Nov 01 2013
"Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
```On Friday, 1 November 2013 at 18:44:23 UTC, Philippe Sigaud wrote:
reduce!( (result, elem) => result + (elem[0]-elem[1])^^2
)(zippedRange, 0)

This is really where my problem arose. I understood everything
up
to here, but I sort of had this idea, "hey zip returns a tuple
so
that somehow the compiler
was going to figure out for me that function(e) has two values"
and is thus
a binary function so this should work (the 0.0 on the end was
my
start value):

reduce!(function(e) { return (e[1]-e[0])*(e[1]-e[0]); })(0.0)

However, of course the compiler see's the tuple as just one
value
- which is where I made my mistake.

The problem is not tuple, it's that reduce needs a binary
function to work.

Yes, that is more or less what I was trying to say. I was
figuring that the compiler could figure out that 'e' was really a
pair of values, thus making function(e) binary.  Of course, that
is asking too much from the compiler.
```
Nov 01 2013
Philippe Sigaud <philippe.sigaud gmail.com> writes:
```What I'm trying to explain is that reduce takes two arguments: the growing
value and the current front. In your case, the current front is indeed a
2-tuple, but that's an unrelated issue.

You're trying to get:

reduce!( (firstElemOfPair, secondElemOfPair) => ...) (range)

to work, whereas reduce signature is:

reduce!( (onGoingValue, elem) => ...) (range)
```
Nov 01 2013
"Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
```On Friday, 1 November 2013 at 20:08:15 UTC, Philippe Sigaud wrote:
What I'm trying to explain is that reduce takes two arguments:
the growing
value and the current front. In your case, the current front is
indeed a
2-tuple, but that's an unrelated issue.

You're trying to get:

reduce!( (firstElemOfPair, secondElemOfPair) => ...) (range)

to work, whereas reduce signature is:

reduce!( (onGoingValue, elem) => ...) (range)

OK, NOW I understand what you were trying to point out. The
function has to take the running sum (in my case) as one of the
arguments.

```
Nov 02 2013
"bearophile" <bearophileHUGS lycos.com> writes:
```Craig Dillabaugh:

I know I could use a simple foreach loop with my zip command, or
even std.numeric.euclidean( ... ), but I am trying to be cute
here!

import std.stdio, std.algorithm, std.range, std.math,
std.functional;

alias sum(T) = curry!(reduce!q{a + b}, cast(T)0);

double euclidDistance(double[] xs, double[] ys)
in {
assert(xs.length == ys.length);
} body {
return zip(xs, ys)
.map!(xy => (xy[0] - xy[1]) ^^ 2)
.sum!double
.sqrt;
}

void main() {
auto xs = [0.0,  1.0, 0.1];
auto ys = [1.0, -1.0, 0.0];
euclidDistance(xs, ys).writeln;
}

Bye,
bearophile
```
Oct 31 2013
"bearophile" <bearophileHUGS lycos.com> writes:
``` alias sum(T) = curry!(reduce!q{a + b}, cast(T)0);

double euclidDistance(double[] xs, double[] ys)
in {
assert(xs.length == ys.length);
} body {
return zip(xs, ys)
.map!(xy => (xy[0] - xy[1]) ^^ 2)
.sum!double
.sqrt;
}

void main() {
auto xs = [0.0,  1.0, 0.1];
auto ys = [1.0, -1.0, 0.0];
euclidDistance(xs, ys).writeln;
}

In D functions are written in camelCase like euclidDistance,