## 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,

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

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

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:clipThanks, I will try both your, and Bearophile's ideas and see if I can figure out how they work. CraigCheers, Craig

Oct 31 2013

On Thu, Oct 31, 2013 at 8:59 PM, Craig Dillabaugh < cdillaba cg.scs.carleton.ca> wrote: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.Thanks, I will try both your, and Bearophile's ideas and see if I can figure out how they work.

Nov 01 2013

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

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: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.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)Thanks, I will try both your, and Bearophile's ideas and see if I can figure out how they work.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

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

On Friday, 1 November 2013 at 18:44:23 UTC, Philippe Sigaud wrote:reduce!( (result, elem) => result + (elem[0]-elem[1])^^2 )(zippedRange, 0)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.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

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

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

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

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