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

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
>

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

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

> 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

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.

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

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.

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.

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.