Strange output

[H. S. Teoh]

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!