higher-order funcs for ranges (with usual interface)

[Lars T. Kyllingstad]

On Wed, 02 Feb 2011 18:38:02 +0100, spir wrote:

> On 02/02/2011 02:18 PM, Lars T. Kyllingstad wrote:
>> On Wed, 02 Feb 2011 13:26:39 +0100, spir wrote:
>>
>>> Hello,
>>>
>>> This bit of code for arrays:
>>>
>>> Out[] map (In,Out) (In[] input, Out delegate (In) f) {
>>>       Out[] output = new Out[](input.length); foreach (i,item ; input)
>>>           output [i] = f(item);
>>>       return output;
>>> }
>>> unittest {
>>>       char character (uint code) {return cast(char)code;} uint[] codes
>>>       = [0x61,0x62,0x63];
>>>       // functional style
>>>       writeln(map(codes,&character));    // "abc" // OO style
>>>       writeln(codes.map(&character));     // "abc"
>>> }
>>>
>>> How to write this for ranges? [...]
>>>
>>> For ranges, I'm looking for something similar to:
>>>       Range!Out map (In,Out) (Range!In input, Out delegate (In) f)
>>>       {...}
>>> Indeed, the compiler should understand that Range!T is a type id just
>>> like T[].
>>
>> I don't think it's possible to do it exactly as you describe.  I mean,
>> Range in that case can be anything, and you can't always return a range
>> of the same kind.
> 
> Right. The output range's ElementType is given by f's return type. As
> you say, the "kind" of range may change. Even if it's the same, how
> could one express that: <range_which-elements-are-of-type-T>,
> syntactically and in the param set, just like
> <array_which-elements-are-of-type-> is written "T[]"? Currently, we must
> (1) declare the range type as template param, which is a bit redondant
> because the ElementType must also be given, (2) add some 'is' horror
> code:
>       if (isInputRange!Range && is(ElementType!Range : In))
> I guess the only solution would be for the compiler to support a kind of
> reange type syntax?

I'm not sure I understand what you mean here.  Perhaps you're looking for 
something like concepts, which have been discussed for both D and C++0x 
but rejected in both languages:

    http://en.wikipedia.org/wiki/Concept_%28generic_programming%29


Anyway, if the source and target range are of the same (known) kind, 
something like this should work:

    struct MyRange(T) { ... }

    MyRange!Out map(In, Out)(MyRange!In input, Out delegate(In) f)
    {
        ...
    }

If they are of different kinds, but still known, this should work:

    struct MySourceRange(T) { ... }
    struct MyTargetRange(T) { ... }

    MyTargetRange!Out map(In, Out)
        (MySourceRange!In input, Out delegate(In) f)
    {
        ...
    }

Note that I am only talking about what the compiler should be able to 
figure out through IFTI (implicit function template instantiation), and 
not about actual implementation.


>>   Two possibilities are, you can do it eagerly,
>>
>>    Out[] map(Range, In, Out)(Range input, Out delegate(In) f)
>>        if (isInputRange!Range&&  is(ElementType!Range : In))
>>    {
>>        ...
>>    }
> 
> OK.
> 
>> or you can do it lazily by defining your own map range (untested):
>>
>>    struct Map(Range, In, Out)
>>        if (isInputRange!Range&&  is(ElementType!Range : In)
>>    {
>>        Range input;
>>        Out delegate(In) f;
>>
>>        @property bool empty() { return input.empty; }
>>
>>        // Inefficient, should cache front... @property Out front() {
>>        return f(input.front); }
>>
>>        void popFront() { input.popFront(); }
>>    }
> 
> That's similar to what I did.
> 
>>    Map!(Range, Out) map(Range, In, Out)(Range input, Out delegate(In)
>>    f)
>>        if (isInputRange!R&&  is(ElementType!Range : In)
>>    {
>>        return typeof(return)(input, f);
>>    }
> 
> What's the point of map, then? My version initially had a 'MapRange'
> defined as static struct template inside map, but then map just
> instanciated it, so I suppressed map alltogether, letting the user
> write:
> 	auto r2 = MapRange!(R1, In, Out)(input, f);
> which is not more complicated than calling the func, I guess.

map() is just a helper function.   Unlike struct literals/constructors, 
functions can make use of IFTI, which makes for much prettier code:

    // The range from my example, without map()
    auto result =
        Map!(SomeRange!int, int, bool)(someRange, someDelegate);

    // The range from my example, with map()
    auto result = map(someInputRange, someDelegate);

This has become a quite common idiom in Phobos.  std.range, for instance, 
is littered with helper functions like this:

  Retro, retro()
  Stride, stride()
  Chain, chain()
  ...

The list goes on.

-Lars