www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - What is "FilterResult" type?

reply "Bahman Movaqar" <b.movaqar gmail.com> writes:
 From what I can gather the output of `std.algorithm.iteration : 
filter` is a `FilterResult` type.
I need a bit of help dealing with this type:
   1. Why this type is there in the first place instead of simply 
using the type of input range?
   2. Where is the documentation for this type?  The documentation 
always uses `auto` for `filter` return values.
   3. How can I convert this type back into a range?

Thanks.
Sep 08 2015
parent reply "cym13" <cpicard openmailbox.org> writes:
On Tuesday, 8 September 2015 at 09:48:35 UTC, Bahman Movaqar 
wrote:

 From what I can gather the output of `std.algorithm.iteration : 
 filter` is a `FilterResult` type.
 I need a bit of help dealing with this type:
   1. Why this type is there in the first place instead of 
 simply using the type of input range?
   2. Where is the documentation for this type?  The 
 documentation always uses `auto` for `filter` return values.
   3. How can I convert this type back into a range?

 Thanks.


Filter is a template and returns a FilterResult range which is 
used to lazily compute the result. This behaviour is the same for 
map and the majority of functions in std.algorithm.

It is an input range really (ie: it has front, popFront and 
empty). You can chain it just like any other range with other 
functions and normally don't have to know the exact type (which 
would be complicated since it is a templated thing).

To store it in a variable if you don't know the exact type you 
can use auto to use type deduction. If you need the type (for a 
template for example) you can then use typeof.

Example:

void main() {
     import std.stdio: writeln;
     import std.algorithm: filter, map;

     int[] arr = [1, 2, 3, 4, 5];
     auto result = arr.filter!(x => x%2); // filter out even 
numbers

     result.writeln; // Writes [1, 3, 5];

     // What is the type of result?
     typeid(result).writeln;
     //-> temporary.main.FilterResult!(__lambda2, 
int[]).FilterResult

     // Map takes a range, this works because result is one.
     auto result2 = result.map!(x => 2*x);
     //-> temporary.main.MapResult!(__lambda3, 
FilterResult!(__lambda2,int[])).MapResult

     // Here is the reason you don't want to type them yourself. 
auto FTW!
     typeid(result).writeln; // main.FilterResult!(__lambda2, 
int[]).FilterResult

     // You can put it back in an array too
     import std.array: array;
     int[] resultArr = result2.array;
}

If you want more precise documentation the best is to look to the 
source code (/usr/include/dlang/dmd/std/algorithm/iteration if 
you are on linux).
Sep 08 2015
parent reply "Bahman Movaqar" <b.movaqar gmail.com> writes:
On Tuesday, 8 September 2015 at 10:08:03 UTC, cym13 wrote:

 Filter is a template and returns a FilterResult range which is 
 used to lazily compute the result. This behaviour is the same 
 for map and the majority of functions in std.algorithm.


Ah...now it makes sense why use a proxy to the results.


 It is an input range really (ie: it has front, popFront and 
 empty). You can chain it just like any other range with other 
 functions and normally don't have to know the exact type (which 
 would be complicated since it is a templated thing).


I agree.  Some types are better left unspecified; like some 300+ 
characters long type signatures one would get from a generic 
Scala function :-D

However, I have made this a strict practice of mine to specify 
the full signature of my public API.  I suppose, if I want to be 
pedantic, I have to realise the lazy value first and pass the 
resulting array out.  Is this correct?


 To store it in a variable if you don't know the exact type you 
 can use auto to use type deduction.


True.


 Example:


Great.  The usage is crystal clear to me now.


 If you want more precise documentation the best is to look to 
 the source code (/usr/include/dlang/dmd/std/algorithm/iteration 
 if you are on linux).


Thanks for the help and pointers.
Sep 08 2015
next sibling parent "Edwin van Leeuwen" <edder tkwsping.nl> writes:
On Tuesday, 8 September 2015 at 11:08:59 UTC, Bahman Movaqar 
wrote:

 On Tuesday, 8 September 2015 at 10:08:03 UTC, cym13 wrote:

 Filter is a template and returns a FilterResult range which is 
 used to lazily compute the result. This behaviour is the same 
 for map and the majority of functions in std.algorithm.




You can also use .array to (greedily) evaluate the results, which 
(for filter) will return a range of the same type as went in:

void main()
{
     import std.array : array;
     int[] arr = [1, 2, 3, 4, 5];
     int[] result = arr.filter!(x => x%2).array;
}
Sep 08 2015
prev sibling next sibling parent "cym13" <cpicard openmailbox.org> writes:
On Tuesday, 8 September 2015 at 11:08:59 UTC, Bahman Movaqar 
wrote:

 However, I have made this a strict practice of mine to specify 
 the full signature of my public API.  I suppose, if I want to 
 be pedantic, I have to realise the lazy value first and pass 
 the resulting array out.  Is this correct?


Yes, using an array will work here, but if you are designing a 
library then I'd prefer that you don't force me into being non 
lazy where I could be just because you want to have a clear type: 
laziness is a virtue, reducing possibilities isn't a great idea.

What I would do is a designated wrapper template which will give 
you a clear type while still being lazy: exactly what 
FilterResult and MapResult are.
Sep 08 2015
prev sibling next sibling parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Tuesday, September 08, 2015 11:08:57 Bahman Movaqar via Digitalmars-d-learn
wrote:

 However, I have made this a strict practice of mine to specify
 the full signature of my public API.


If your API returns ranges, that's general not only bad practice but
arguably impossible. Most range-based functions purposefully return
Voldemort types (the type is declared inside of the function, meaning that
you cannot name it). FilterResult really should be to, but I think that it's
not in order to work around a bug. Regardless, it's private and should never
be used explicitly.

If you want to put a range type in an API, you're forced to do stuff like

typeof(rangeFunc!someFunc(SomeOtherRange.init)) myFunc(int);

If you're returning a range, you should be returning auto. The documentation
should then say whether it's an input range, forward range, etc. - but you
should pretty much never be using range types explicitly. Your code will
become an unmaintainable, unreadable mess if you try. And really, it's
unnecessary. Simply having the documentation say what sort of range it's
returning is plenty. Exact types are unnecessary in this case and
counterproductive.

- Jonathan M Davis
Sep 08 2015
parent reply "Bahman Movaqar" <b.movaqar gmail.com> writes:
On Tuesday, 8 September 2015 at 18:45:33 UTC, Jonathan M Davis 
wrote:

 If you're returning a range, you should be returning auto.


 Jonathan,  cym13 and  Meta
It's reasonable to use `auto`.  However there are times when you 
need to pass the `auto` value to another function and the 
receiving function needs to know the type of its input arguments.

In other news:
Consider the following piece of code.  *Please note that I am 
aware that the simple problem introduced can be solved in several 
ways which are more efficient.*

     immutable struct FooBar {
       int x;
       int y;
     }
     immutable(FooBar)[] foobars = [
       FooBar(60, 100),
       FooBar(8, 20),
       FooBar(9, 15)
     ];
     int[] nums = [20, 40, 55];

     //////////////////////////////////////////
     // find FooBars which:
     //   - x * y is greater than any `num`
     //   - x and y are smaller than any `num`
     //////////////////////////////////////////
     auto result = reduce!(
       (acc, num) => acc.filter!(
         fb => (fb.x < num && fb.y < num) && (fb.x * fb.y > num)
       )
     )(foobars, nums);
     //
     assert(result[0].x == 9 && result[0].y == 15);

This fails to compile with the following message:

     Error: static assert  "Incompatible function/seed/element: 
test.__unittestL40_4.__lambda1/immutable(FooBar)[]/int"
     /usr/include/dmd/phobos/std/algorithm/iteration.d(2518):      
   instantiated from here: reduceImpl!(false, int[], 
immutable(FooBar)[])
     /usr/include/dmd/phobos/std/algorithm/iteration.d(2502):      
   instantiated from here: reducePreImpl!(int[], 
immutable(FooBar)[]) test.d(56):        instantiated from here: 
reduce!(immutable(FooBar)[], int[])

The only way to make it work is `.array.idup` the output of 
`filter`.  For example:

     auto result = reduce!(
       (acc, num) => acc.filter!(
         fb => (fb.x < num && fb.y < num) && (fb.x * fb.y > num)
       ).array.idup
     )(foobars, nums);

Honestly, I cannot comprehend anything out of this; why I had to 
realise the lazy value and `idup` it for it to become usable by 
`reduce`?
Does this mean that I am simply missing something obvious?
Sep 09 2015
next sibling parent reply "Sebastiaan Koppe" <mail skoppe.eu> writes:
On Wednesday, 9 September 2015 at 07:19:06 UTC, Bahman Movaqar 
wrote:

 The only way to make it work is `.array.idup` the output of 
 `filter`.  For example:

     auto result = reduce!(
       (acc, num) => acc.filter!(
         fb => (fb.x < num && fb.y < num) && (fb.x * fb.y > num)
       ).array.idup
     )(foobars, nums);

 Honestly, I cannot comprehend anything out of this; why I had 
 to realise the lazy value and `idup` it for it to become usable 
 by `reduce`?
 Does this mean that I am simply missing something obvious?


Reduce takes the seed, calls your function, and your function 
returns a new seed.

What is going wrong is that the types aren't the same. That is, 
the type of the seed you supplied - `typeof(foobars)` - isn't the 
type that your function returns - `typeof(acc.filter!...)`.

`array()` fixes that, no idea why you need `idup()` though.

OT: I wonder, is reduce able to call a different templated 
version of reduce?
Sep 09 2015
parent "Bahman Movaqar" <b.movaqar gmail.com> writes:
On Wednesday, 9 September 2015 at 07:59:57 UTC, Sebastiaan Koppe 
wrote:

 What is going wrong is that the types aren't the same. That is, 
 the type of the seed you supplied - `typeof(foobars)` - isn't 
 the type that your function returns - `typeof(acc.filter!...)`.


Alright.  So, `reduce` initial seed is an `array` while the 
output of `filter` is a `FilterResult`.  I suppose it makes sense 
to realise it (`.array`) before passing to the next round.

I was under the impression that `reduce` understands 
`FilterResult` and realises it internally; it doesn't and I was 
wrong.  Though I believe it would have been more intuitive if it 
did.

Thanks for the help.


 `array()` fixes that, no idea why you need `idup()` though.


True --`idup` was not required.  My mistake.
Sep 09 2015
prev sibling next sibling parent reply "cym13" <cpicard openmailbox.org> writes:
On Wednesday, 9 September 2015 at 07:19:06 UTC, Bahman Movaqar 
wrote:

 On Tuesday, 8 September 2015 at 18:45:33 UTC, Jonathan M Davis 
 wrote:

 [...]


  Jonathan,  cym13 and  Meta
 It's reasonable to use `auto`.  However there are times when 
 you need to pass the `auto` value to another function and the 
 receiving function needs to know the type of its input 
 arguments.

 In other news:
 Consider the following piece of code.  *Please note that I am 
 aware that the simple problem introduced can be solved in 
 several ways which are more efficient.*

     immutable struct FooBar {
       int x;
       int y;
     }
     immutable(FooBar)[] foobars = [
       FooBar(60, 100),
       FooBar(8, 20),
       FooBar(9, 15)
     ];
     int[] nums = [20, 40, 55];

     //////////////////////////////////////////
     // find FooBars which:
     //   - x * y is greater than any `num`
     //   - x and y are smaller than any `num`
     //////////////////////////////////////////
     auto result = reduce!(
       (acc, num) => acc.filter!(
         fb => (fb.x < num && fb.y < num) && (fb.x * fb.y > num)
       )
     )(foobars, nums);
     //
     assert(result[0].x == 9 && result[0].y == 15);

 This fails to compile with the following message:

     Error: static assert  "Incompatible function/seed/element: 
 test.__unittestL40_4.__lambda1/immutable(FooBar)[]/int"
     /usr/include/dmd/phobos/std/algorithm/iteration.d(2518):
   instantiated from here: reduceImpl!(false, int[], 
 immutable(FooBar)[])
     /usr/include/dmd/phobos/std/algorithm/iteration.d(2502):
   instantiated from here: reducePreImpl!(int[], 
 immutable(FooBar)[]) test.d(56):        instantiated from here: 
 reduce!(immutable(FooBar)[], int[])

 The only way to make it work is `.array.idup` the output of 
 `filter`.  For example:

     auto result = reduce!(
       (acc, num) => acc.filter!(
         fb => (fb.x < num && fb.y < num) && (fb.x * fb.y > num)
       ).array.idup
     )(foobars, nums);

 Honestly, I cannot comprehend anything out of this; why I had 
 to realise the lazy value and `idup` it for it to become usable 
 by `reduce`?
 Does this mean that I am simply missing something obvious?


You are using reduce in a weird way here... I find it normal to 
have to use weird internal tricks if you are trying weird things. 
The way I would have written it is:

auto result = foobars.filter!(fb => nums.all!(n => (fb.x * fb.y) 

 n))


                      .filter!(fb => nums.all!(n => fb.x < n && 
fb.y < n));

Here you don't have any weird and completely unreadable reduce 
construct and don't have to realize the lazy check as 
std.algorithm.searching.all is lazy too.
Sep 09 2015
parent reply "Bahman Movaqar" <b.movaqar gmail.com> writes:
On Wednesday, 9 September 2015 at 08:29:20 UTC, cym13 wrote:

 You are using reduce in a weird way here...


Oh?  Perhaps it was all because of the lame example I used :-)
The real problem I was trying to solve, source of which I just 
pushed[1], was the `select` method on line 130.  Is this 
idiomatic or still weird?


 The way I would have written it is:

 auto result = foobars.filter!(fb => nums.all!(n => (fb.x * 
 fb.y) > n))
                      .filter!(fb => nums.all!(n => fb.x < n && 
 fb.y < n));


For the lame example I gave, something similar occurred to me at 
first; but then I thought 4 `filter`s (assuming `all` is simply a 
`filter`) might be non-idiomatic as it might incur some 
performance penalty.


 Here you don't have any weird and completely unreadable reduce 
 construct and don't have to realize the lazy check as 
 std.algorithm.searching.all is lazy too.


True.  But is pumping the output of `filter` as the seed into 
`reduce` really considered weird usage!?

[1] 
https://github.com/bahmanm/d-etudes/blob/master/source/e002/models.d
Sep 09 2015
next sibling parent reply "cym13" <cpicard openmailbox.org> writes:
On Wednesday, 9 September 2015 at 11:30:26 UTC, Bahman Movaqar 
wrote:

 For the lame example I gave, something similar occurred to me 
 at first; but then I thought 4 `filter`s (assuming `all` is 
 simply a `filter`) might be non-idiomatic as it might incur 
 some performance penalty.


As those are templates I don't think you'd have any overhead ; I 
may be wrong about that but the whole point of such constructs is 
to allow what Walter poetically called “memory disallocation”.

https://www.youtube.com/watch?v=znjesAXEEqw


 True.  But is pumping the output of `filter` as the seed into 
 `reduce` really considered weird usage!?


I don't think it is really weird per se, I just can't think of a 
case where there isn't a better way to do it. I find it 
completely unreadable frankly, and I generally avoid reduce when 
I can because it is not UFCS-able. This is only personal opinion 
though.
Sep 09 2015
parent "Bahman Movaqar" <b.movaqar gmail.com> writes:
On Wednesday, 9 September 2015 at 13:16:49 UTC, cym13 wrote:

 True.  But is pumping the output of `filter` as the seed into 
 `reduce` really considered weird usage!?


 I don't think it is really weird per se, I just can't think of 
 a case where there isn't a better way to do it. I find it 
 completely unreadable frankly, and I generally avoid reduce 
 when I can because it is not UFCS-able. This is only personal 
 opinion though.


Now I see your point.  I too find fold/reduce the least 
transparent verb of the list comprehension.  And certainly your 
point about UFCS adds to it.
Sep 11 2015
prev sibling parent "deed" <none none.none> writes:
On Wednesday, 9 September 2015 at 11:30:26 UTC, Bahman Movaqar 
wrote:

 On Wednesday, 9 September 2015 at 08:29:20 UTC, cym13 wrote:

 The way I would have written it is:

 auto result = foobars.filter!(fb => nums.all!(n => (fb.x * 
 fb.y) > n))
                      .filter!(fb => nums.all!(n => fb.x < n && 
 fb.y < n));


 For the lame example I gave, something similar occurred to me 
 at first; but then I thought 4 `filter`s (assuming `all` is 
 simply a `filter`) might be non-idiomatic as it might incur 
 some performance penalty.


Note that this can easily be rewritten with only one `filter` and 
one `all`:

auto result = foobars.filter!(
                 fb => nums.all!(
                     n => fb.x * fb.y > n
                       && fb.x < n
                       && fb.y < n));
Sep 09 2015
prev sibling parent reply "Atila Neves" <atila.neves gmail.com> writes:
On Wednesday, 9 September 2015 at 07:19:06 UTC, Bahman Movaqar 
wrote:

 On Tuesday, 8 September 2015 at 18:45:33 UTC, Jonathan M Davis 
 wrote:

 If you're returning a range, you should be returning auto.


  Jonathan,  cym13 and  Meta
 It's reasonable to use `auto`.  However there are times when 
 you need to pass the `auto` value to another function and the 
 receiving function needs to know the type of its input 
 arguments.


No, it doesn't. It needs to know what the compile-time interface 
is, i.e. what it can do with that type. If the type in question 
happens to be an InputRange, then the consumer function would be:

void func(R)(R range) if(isInputRange!R) { ... }

instead of using a concrete type like this:

void func(MyType range) { ... }

That way you can change range types and `func` doesn't care.

Atila
Sep 09 2015
parent "Bahman Movaqar" <b.movaqar gmail.com> writes:
On Wednesday, 9 September 2015 at 09:08:28 UTC, Atila Neves wrote:

 No, it doesn't. It needs to know what the compile-time 
 interface is, i.e. what it can do with that type. If the type 
 in question happens to be an InputRange, then the consumer 
 function would be:

 void func(R)(R range) if(isInputRange!R) { ... }

 instead of using a concrete type like this:

 void func(MyType range) { ... }

 That way you can change range types and `func` doesn't care.


Ah...makes sense.  Thanks.
Sep 09 2015
prev sibling parent "Meta" <jared771 gmail.com> writes:
On Tuesday, 8 September 2015 at 11:08:59 UTC, Bahman Movaqar 
wrote:

 However, I have made this a strict practice of mine to specify 
 the full signature of my public API.  I suppose, if I want to 
 be pedantic, I have to realise the lazy value first and pass 
 the resulting array out.  Is this correct?


If you _really_ want to specify the return type, you can import 
std.range.interfaces[1] and use the appropriate return type 
(e.g., InputRange!int, RandomAccessFinite!char, etc.) and then 
append a `.inputRangeObject` to the end of your range chain.

Ex:

import std.algorithm;
import std.range;

InputRange!int doRangeyThings(R)(R r)
if (isInputRange!R)
{
	return r.filter!(x => !(x & 1))
			.map!(x => x * 2)
			.inputRangeObject;
}

void main()
{
	auto n = [1, 2, 3, 4];
	auto m = n.doRangeyThings();
	assert(is(typeof(m) == InputRange!int));
	assert(m.equal([4, 8]));
}

You should use this sparingly, however. The types in 
std.range.interfaces are interfaces that allow you to combine 
ranges with runtime polymorphism, and you have to pay the 
corresponding price for that, namely, you'll be hitting the GC 
and the virtual functions entail a speed hit.




1. http://dlang.org/phobos/std_range_interfaces.html
Sep 08 2015