On Fri, Jun 07, 2013 at 09:10:53PM +0200, Daemon wrote:
> The following program is supposed to print out only numbers that are less than 5, yet the number 63 gets printed.

On Fri, Jun 07, 2013 at 09:14:00PM +0200, Daemon wrote:
> >auto de = find!(delegate(a) { return a < 5; })([10, 11, 15, 16,
> >27, 20, 2, -4, -17, 8, 64, 6]);
> 
> Just a clarification, it prints out 64 with the input above, I changed it later just to test it and forgot to update the rest.

This should not be surprising. Please see my comments below:


> module main;
> 
> import std.stdio;
> import std.conv;
> 
> int main(string[] argv)
> {
> 	auto de = find!(delegate(a) { return a < 5; })([10, 11, 15, 16, 27,
> 20, 2, -4, -17, 8, 64, 6]);
> 

OK, so here 'de' is assigned whatever is returned by 'find', and the following loop prints out its contents. The question then is, what does find() return?


> 	foreach (int b; de[0 .. $])
> 	{
> 		writeln(b);
> 	}
> 
> 	readln();
> 
>     return 0;
> }
> 
> T[] find(alias pred, T)(T[] input)
> 	if (is(typeof(pred(input[0])) == bool))
> {
> 	for (; input.length > 0; input = input[1 .. $])

OK, so what the above is saying, is that you want to loop over the input array, and reduce it by one element each time (i.e. slice from 1 to the end). So let's look at the input main() is giving it: [10, 11, 15, ...]. So the first time round, we're looking at the entire array, which starts with the element 10.


> 	{
> 		if (pred(input[0]))
> 		{
> 			break;
> 		}

So here, 'pred' is passed the value of input[0]. The first time round, input[0] is 10, so pred returns false: because 10 < 5 is false. So the loop runs again, and the next time round, the array has been shortened to [11, 15, ...]. So now, input[0] is 11, and again, 11 < 5 is false, so the loop keeps running.

Now what happens after the next few iterations, when you get to '2'? At that point, input looks like this: [2, -4, -17, 8, 64, 6]. So input[0] is 2, and since 2 < 5, pred(input[0]) returns true. So the next line says 'break', which means "stop running the loop". Remember that at this point, input is [2, -4, -17, 8, 64, 6]. And then finally:


> 	}
> 	return input;
> }

This says, return input (which is currently [2, -4, -17, 8, 64, 6]). So
going back to main(), we see that 'de' must be [2, -4, -17, 8, 64, 6].
And indeed, that's the output you get.

So the program isn't doing anything wrong. It's just that what you wrote isn't quite what you wanted. :)

It sounds like you wanted to *filter* the array for elements less than 5. So what you need to do is, once you find an element that's 5 or greater, you need to skip over it. However, a D array is a *contiguous* list of elements; there's no such thing as a skipped element in an array. So you can't just return a slice of the original array -- a slice is also a contiguous block of elements; while it *can* give you a "sub-array" view of the original array, it cannot start somewhere, skip over some elements, and then continue.

The easiest solution is to construct a new array that doesn't have the offending elements, maybe something along these lines:

T[] find(alias pred, T)(T[] input)
	if (is(typeof(pred(input[0])) == bool))
{
	// Note this line: we're creating a new array containing only
	// the elements we want.
	T[] result;

	for (; input.length > 0; input = input[1 .. $])
	{
		if (pred(input[0]))
		{
			// Found an element that satisfies our
			// predicate, so append that to the end of our
			// results.
			result ~= input[0];

			// (No break here: we want to look at every
			// element in the input.)
		}
	}

	// N.B.: instead of returning input, which is a slice of the
	// original array, we return the new array we've constructed
	// that only has the elements we want.
	return result;
}

Hope this helps!


T

-- 
Freedom of speech: the whole world has no right *not* to hear my spouting off!

On Friday, 7 June 2013 at 20:06:32 UTC, H. S. Teoh wrote:
> On Fri, Jun 07, 2013 at 09:10:53PM +0200, Daemon wrote:
>> The following program is supposed to print out only numbers that are
>> less than 5, yet the number 63 gets printed.
>
> On Fri, Jun 07, 2013 at 09:14:00PM +0200, Daemon wrote:
>> >auto de = find!(delegate(a) { return a < 5; })([10, 11, 15, 16,
>> >27, 20, 2, -4, -17, 8, 64, 6]);
>> 
>> Just a clarification, it prints out 64 with the input above, I
>> changed it later just to test it and forgot to update the rest.
>
> This should not be surprising. Please see my comments below:
>
>
>> module main;
>> 
>> import std.stdio;
>> import std.conv;
>> 
>> int main(string[] argv)
>> {
>> 	auto de = find!(delegate(a) { return a < 5; })([10, 11, 15, 16, 27,
>> 20, 2, -4, -17, 8, 64, 6]);
>> 
>
> OK, so here 'de' is assigned whatever is returned by 'find', and the
> following loop prints out its contents. The question then is, what does
> find() return?
>
>
>> 	foreach (int b; de[0 .. $])
>> 	{
>> 		writeln(b);
>> 	}
>> 	
>> 	readln();
>> 
>>     return 0;
>> }
>> 
>> T[] find(alias pred, T)(T[] input)
>> 	if (is(typeof(pred(input[0])) == bool))
>> {
>> 	for (; input.length > 0; input = input[1 .. $])
>
> OK, so what the above is saying, is that you want to loop over the input
> array, and reduce it by one element each time (i.e. slice from 1 to the
> end). So let's look at the input main() is giving it: [10, 11, 15, ...].
> So the first time round, we're looking at the entire array, which starts
> with the element 10.
>
>
>> 	{
>> 		if (pred(input[0]))
>> 		{
>> 			break;
>> 		}
>
> So here, 'pred' is passed the value of input[0]. The first time round,
> input[0] is 10, so pred returns false: because 10 < 5 is false. So the
> loop runs again, and the next time round, the array has been shortened
> to [11, 15, ...]. So now, input[0] is 11, and again, 11 < 5 is false, so
> the loop keeps running.
>
> Now what happens after the next few iterations, when you get to '2'? At
> that point, input looks like this: [2, -4, -17, 8, 64, 6]. So input[0]
> is 2, and since 2 < 5, pred(input[0]) returns true. So the next line
> says 'break', which means "stop running the loop". Remember that at this
> point, input is [2, -4, -17, 8, 64, 6]. And then finally:
>
>
>> 	}
>> 	return input;
>> }
>
> This says, return input (which is currently [2, -4, -17, 8, 64, 6]). So
> going back to main(), we see that 'de' must be [2, -4, -17, 8, 64, 6].
> And indeed, that's the output you get.
>
> So the program isn't doing anything wrong. It's just that what you wrote
> isn't quite what you wanted. :)
>
> It sounds like you wanted to *filter* the array for elements less than
> 5. So what you need to do is, once you find an element that's 5 or
> greater, you need to skip over it. However, a D array is a *contiguous*
> list of elements; there's no such thing as a skipped element in an
> array. So you can't just return a slice of the original array -- a slice
> is also a contiguous block of elements; while it *can* give you a
> "sub-array" view of the original array, it cannot start somewhere, skip
> over some elements, and then continue.
>
> The easiest solution is to construct a new array that doesn't have the
> offending elements, maybe something along these lines:
>
> T[] find(alias pred, T)(T[] input)
> 	if (is(typeof(pred(input[0])) == bool))
> {
> 	// Note this line: we're creating a new array containing only
> 	// the elements we want.
> 	T[] result;
>
> 	for (; input.length > 0; input = input[1 .. $])
> 	{
> 		if (pred(input[0]))
> 		{
> 			// Found an element that satisfies our
> 			// predicate, so append that to the end of our
> 			// results.
> 			result ~= input[0];
>
> 			// (No break here: we want to look at every
> 			// element in the input.)
> 		}
> 	}
>
> 	// N.B.: instead of returning input, which is a slice of the
> 	// original array, we return the new array we've constructed
> 	// that only has the elements we want.
> 	return result;
> }
>
> Hope this helps!
>
>
> T

Thanks a lot for the clarification of the arrays, that really got me confused for a while!