www.digitalmars.com         C & C++   DMDScript  

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

reply "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
next sibling parent reply 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
parent reply "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
parent reply 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).
std.algorithm.reduce provides both overloads.

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. Access to the
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



 next sibling parent  "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 
 Haskell.


It's already in Bugzilla:
http://d.puremagic.com/issues/show_bug.cgi?id=11084

Bye,
bearophile



 Nov 01 2013



prev sibling  parent reply "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).
 std.algorithm.reduce provides both overloads.

 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. 
 Access to the
 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 
 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



  parent reply 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



  parent reply "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



  parent reply 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



  parent  "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.

Thanks for your patience.



 Nov 02 2013



prev sibling  parent reply "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



  parent  "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, 
instead of euclid_distance.

Function pre-conditions and post-conditions are generally better 
put in the pre and post part of functions.

I have defined a sum because it's a generally useful function, 
but it's a toy because it assumes cast(T)0 as the identity 
element of the monoid with the plus operator.

Bye,
bearophile



 Oct 31 2013