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? I mean, with the same kind of interface to client code (not the interface of std.algo.map).
And is there a way to write it so that it works both for ranges and other kinds of sequences (arrays, strings); or even for anything "iterable" (AA, set, list, tree...).

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[].

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

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.  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))
  {
      ...
  }

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(); }
  }

  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);
  }

-Lars

On Wed, 02 Feb 2011 13:18:07 +0000, Lars T. Kyllingstad wrote:

> [...]
> 
>   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(); }
>   }
> 
>   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);
>   }

Oops, seems i missed a few closing parentheses on the template constraints.

-Lars

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?

>   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.

> -Lars

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

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

On 02/03/2011 08:41 AM, Lars T. Kyllingstad wrote:
> On Wed, 02 Feb 2011 18:38:02 +0100, spir wrote:

>> 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

Yes, I know about concepts ;-) (and typestates, and such). That's not what I mean but I could not find how to express it. What I have in mind is a way to simply express <range of T> just like <array of T> is expressed by "T[]". But indeed the issue is there is only one type of array of T, while there are an infinity of types of ranges of T.
Your solution below is a good alternative.

> 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.

Right, this is more or less what I was looking for. And I think I can restrict cases to ranges beeing of the same "kind". If necessary, the result can then be mapped onto another kind of range (hopefully lazily).
The only "un-workaround-able" situation is, I guess, when the source range is infinite ;-)


Denis
-- 
_________________
vita es estrany
spir.wikidot.com

On Thu, 03 Feb 2011 13:05:00 +0100, spir wrote:

> On 02/03/2011 08:41 AM, Lars T. Kyllingstad wrote:
>> On Wed, 02 Feb 2011 18:38:02 +0100, spir wrote:
> 
>>> 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
> 
> Yes, I know about concepts ;-) (and typestates, and such). That's not
> what I mean but I could not find how to express it. What I have in mind
> is a way to simply express <range of T> just like <array of T> is
> expressed by "T[]". But indeed the issue is there is only one type of
> array of T, while there are an infinity of types of ranges of T.
> Your solution below is a good alternative.
> 
>> 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.
> 
> Right, this is more or less what I was looking for. And I think I can restrict cases to ranges beeing of the same "kind". If necessary, the result can then be mapped onto another kind of range (hopefully lazily). The only "un-workaround-able" situation is, I guess, when the source range is infinite ;-)

Why the reluctance to use template constraints?  They're so flexible! :)

-Lars

On 02/03/2011 01:17 PM, Lars T. Kyllingstad wrote:
> Why the reluctance to use template constraints?  They're so flexible! :)

I cannot stand the "is()" idiom/syntax ;-) Dunno why. Would happily get rid of it in favor of type-classes (built eg as an extension to current interfaces). For instance, instead of:

    void func (T) (T t)
        if (is(someConstraint1) && is(someConstraint2))
    {
        ...
    }

use:

    void func (SomeTypeClass T) (T t)
    {
        ...
    }

For instance (untested):

    void func (T) (T t)
        if (isInputRange(T) && is(ElementType!T == E))
-->
    void func (InputRange!E T) (T t)

where InputRange is a (templated) interface / type-class.

Type-class checks on /type/ /template/ parameters (as opposed to type checks on regular value parameters) would be performed structurally (as opposed to nominally). D knows how to do this, since that's what it needs to perform when checking is() constraints.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

On Thu, 03 Feb 2011 13:53:44 +0100, spir wrote:

> On 02/03/2011 01:17 PM, Lars T. Kyllingstad wrote:
>> Why the reluctance to use template constraints?  They're so flexible! :)
> 
> I cannot stand the "is()" idiom/syntax ;-) Dunno why. Would happily get
> rid of it in favor of type-classes (built eg as an extension to current
> interfaces). For instance, instead of:
> 
>      void func (T) (T t)
>          if (is(someConstraint1) && is(someConstraint2))
>      {
>          ...
>      }
> 
> use:
> 
>      void func (SomeTypeClass T) (T t)
>      {
>          ...
>      }
> 
> For instance (untested):
> 
>      void func (T) (T t)
>          if (isInputRange(T) && is(ElementType!T == E))
> -->
>      void func (InputRange!E T) (T t)
> 
> where InputRange is a (templated) interface / type-class.
> 
> Type-class checks on /type/ /template/ parameters (as opposed to type
> checks on regular value parameters) would be performed structurally (as
> opposed to nominally). D knows how to do this, since that's what it
> needs to perform when checking is() constraints.

I agree that is() is rather ugly.  Same with __traits.  If you haven't already done so, I suggest you vote up this issue:

  http://d.puremagic.com/issues/show_bug.cgi?id=3702

Anyway, you can hide is()'s ugliness in the most common cases, though, by defining new templates.  For instance, I wouldn't mind having the following in std.range as an overload of isInputRange:

  template isInputRange(R, T)
  {
      enum isInputRange = isInputRange!R && is(ElementType!R == T);
  }

Then, you'd simply write

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

-Lars

On 02/03/2011 02:25 PM, Lars T. Kyllingstad wrote:
> On Thu, 03 Feb 2011 13:53:44 +0100, spir wrote:
>
>> On 02/03/2011 01:17 PM, Lars T. Kyllingstad wrote:
>>> Why the reluctance to use template constraints?  They're so flexible!
>>> :)
>>
>> I cannot stand the "is()" idiom/syntax ;-) Dunno why. Would happily get
>> rid of it in favor of type-classes (built eg as an extension to current
>> interfaces). For instance, instead of:
>>
>>       void func (T) (T t)
>>           if (is(someConstraint1)&&  is(someConstraint2))
>>       {
>>           ...
>>       }
>>
>> use:
>>
>>       void func (SomeTypeClass T) (T t)
>>       {
>>           ...
>>       }
>>
>> For instance (untested):
>>
>>       void func (T) (T t)
>>           if (isInputRange(T)&&  is(ElementType!T == E))
>> -->
>>       void func (InputRange!E T) (T t)
>>
>> where InputRange is a (templated) interface / type-class.
>>
>> Type-class checks on /type/ /template/ parameters (as opposed to type
>> checks on regular value parameters) would be performed structurally (as
>> opposed to nominally). D knows how to do this, since that's what it
>> needs to perform when checking is() constraints.
>
> I agree that is() is rather ugly.  Same with __traits.  If you haven't
> already done so, I suggest you vote up this issue:
>
>    http://d.puremagic.com/issues/show_bug.cgi?id=3702

Done!
(I did not get all the details 'cause no time for a deep look, but anything impulsed by the motivation of getting rid of is() and __traits can hardly be a Bad Thing ;-)

What do you think of type classes, as an alternative to Don's proposal in issue #3702.
See also "Type Classes as Objects and Implicits":
http://ropas.snu.ac.kr/~bruno/papers/TypeClasses.pdf

> Anyway, you can hide is()'s ugliness in the most common cases, though, by
> defining new templates.  For instance, I wouldn't mind having the
> following in std.range as an overload of isInputRange:
>
>    template isInputRange(R, T)
>    {
>        enum isInputRange = isInputRange!R&&  is(ElementType!R == T);
>    }
>
> Then, you'd simply write
>
>    void func(R)(R range) if (isInputRange!(R, E)) { ... }
>
> -Lars

A great improvement, indeed.

While we're at defining a set of constraints in a template, let us make it an interface / type-class that the E must (structurally) satisfy, and just write:
    void func(InputRange!E R)(R range) { ... }

What do you think?

Note: a template is not always required, I guess:
    void writeElements (Iterable Elements) (Elements elements) {
	foreach (element, elements) {
            write(element,' ');
        }
    }
(In this case, because write is itself generic.)

Denis
-- 
_________________
vita es estrany
spir.wikidot.com