www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Static Length Propagation of Ranges

reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
Is there a generic way to do


typeof(fn(E.init))[] map1(alias fn, E, size_t n)(E[n] container)
{
   import std.algorithm.iteration : map;
   import std.array : array;
   return container[].map!fn.array;
}

 safe pure nothrow unittest
{
   int[42] c;
   auto result = map1!(_ => _^2)(c);
}


but with propagation of length of return value of `f` to a static 
array instead, without having to specialize each range separately?

One less elegant way would be to replace the call to `array` with 
an overload of `std.container.util.make` for static arrays, that 
checks at run-time that the length of the output static array 
matches the length of the input range?
Oct 19 2016
parent reply Meta <jared771 gmail.com> writes:
On Wednesday, 19 October 2016 at 13:59:29 UTC, Nordlöw wrote:

 Is there a generic way to do


 typeof(fn(E.init))[] map1(alias fn, E, size_t n)(E[n] container)
 {
   import std.algorithm.iteration : map;
   import std.array : array;
   return container[].map!fn.array;
 }

  safe pure nothrow unittest
 {
   int[42] c;
   auto result = map1!(_ => _^2)(c);
 }


 but with propagation of length of return value of `f` to a 
 static array instead, without having to specialize each range 
 separately?

 One less elegant way would be to replace the call to `array` 
 with an overload of `std.container.util.make` for static 
 arrays, that checks at run-time that the length of the output 
 static array matches the length of the input range?


Couldn't you do this? Mind you I'm not able to test the code 
right now, but I think it can work with some tweaking.

typeof(fn(E.init))[n] map1(alias fn, E, size_t n)(E[n] container)
{
     import std.algorithm.iteration : map;
     import std.array : array;

     typeof(return) sres;
     return container[].map!fn.copy(sres[]);
}

 safe pure nothrow unittest
{
    int[42] c;
    //result should be a static array of length 42
    auto result = map1!(_ => _^2)(c);
}
Oct 19 2016
parent reply Meta <jared771 gmail.com> writes:
On Wednesday, 19 October 2016 at 18:56:35 UTC, Meta wrote:

 Couldn't you do this? Mind you I'm not able to test the code 
 right now, but I think it can work with some tweaking.

 typeof(fn(E.init))[n] map1(alias fn, E, size_t n)(E[n] 
 container)
 {
     import std.algorithm.iteration : map;
     import std.array : array;

     typeof(return) sres;
     return container[].map!fn.copy(sres[]);
 }

  safe pure nothrow unittest
 {
    int[42] c;
    //result should be a static array of length 42
    auto result = map1!(_ => _^2)(c);
 }


Sorry, that code had a few mistakes. The working code:

import std.algorithm;
import std.range;

typeof(fn(E.init))[n] map1(alias fn, E, size_t n)(E[n] container)
{
     import std.algorithm.iteration : map;
     import std.array : array;

     typeof(return) sres;
     container[].map!fn.copy(sres[]);
     return sres;
}

void main()
{
    int[42] c;
    //result should be a static array of length 42
    auto result = map1!(_ => _^2)(c);
    assert(is(typeof(result) == typeof(c)));
}

https://goo.gl/t9m3YK

I'm actually pretty impressed that this kind of code can be 
written in D.
Oct 19 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 19 October 2016 at 19:01:50 UTC, Meta wrote:

 https://goo.gl/t9m3YK

 I'm actually pretty impressed that this kind of code can be 
 written in D.


Thanks! Add at

https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234
Oct 19 2016
next sibling parent reply Meta <jared771 gmail.com> writes:
On Wednesday, 19 October 2016 at 19:39:46 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 19:01:50 UTC, Meta wrote:

 https://goo.gl/t9m3YK

 I'm actually pretty impressed that this kind of code can be 
 written in D.


 Thanks! Add at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234


I would add this: not sure if it's what you're intending or not, 
but as `in` expands to `const scope` and the semantics of scope 
will probably be changing soon (or more accurately, actually 
implemented), you may want to just go with `const` instead.
Oct 19 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 19 October 2016 at 20:10:04 UTC, Meta wrote:

 Thanks! Add at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234


 I would add this: not sure if it's what you're intending or 
 not, but as `in` expands to `const scope` and the semantics of 
 scope will probably be changing soon (or more accurately, 
 actually implemented), you may want to just go with `const` 
 instead.


Ok, thanks. I updated.
Oct 19 2016
parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 19 October 2016 at 20:13:15 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 20:10:04 UTC, Meta wrote:

 Thanks! Add at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234


 I would add this: not sure if it's what you're intending or 
 not, but as `in` expands to `const scope` and the semantics of 
 scope will probably be changing soon (or more accurately, 
 actually implemented), you may want to just go with `const` 
 instead.


 Ok, thanks. I updated.


BTW: So what about const ref? Will this differ to `in` with 
regards to `scope`? If so will the compiler(s) be smart enough to 
not copy the large stack array when I only qualify with `const`?
Oct 19 2016
parent Meta <jared771 gmail.com> writes:
On Wednesday, 19 October 2016 at 20:15:14 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 20:13:15 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 20:10:04 UTC, Meta wrote:

 Thanks! Add at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234


 I would add this: not sure if it's what you're intending or 
 not, but as `in` expands to `const scope` and the semantics 
 of scope will probably be changing soon (or more accurately, 
 actually implemented), you may want to just go with `const` 
 instead.


 Ok, thanks. I updated.


 BTW: So what about const ref? Will this differ to `in` with 
 regards to `scope`? If so will the compiler(s) be smart enough 
 to not copy the large stack array when I only qualify with 
 `const`?


Well, scope does not imply ref so in both cases a copy will be 
made.
Oct 19 2016
prev sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 19 October 2016 at 19:39:46 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 19:01:50 UTC, Meta wrote:

 https://goo.gl/t9m3YK

 I'm actually pretty impressed that this kind of code can be 
 written in D.


 Thanks! Add at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234


Made it even modular by factoring out arrayN at

https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2200

and used at

https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2215

Code:


ElementType!R[n] arrayN(size_t n, R)(R r)
{
     assert(r.length == n);
     typeof(return) dst;
     import std.algorithm.mutation : copy;
     r.copy(dst[]);
     return dst;
}

typeof(fun(E.init))[n] map(alias fun, E, size_t n)(const E[n] src)
{
     import std.algorithm.iteration : map;
     return src[].map!fun.arrayN!n;
}

 safe pure nothrow unittest
{
     import std.meta : AliasSeq;
     foreach (E; AliasSeq!(int, double))
     {
         enum n = 42;
         E[n] c;
         const result = map!(_ => _^^2)(c);
         static assert(c.length == result.length);
         static assert(is(typeof(result) == const(E)[n]));
     }
}
Oct 20 2016
next sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Thursday, 20 October 2016 at 12:38:40 UTC, Nordlöw wrote:

 ElementType!R[n] arrayN(size_t n, R)(R r)
 {
     assert(r.length == n);
     typeof(return) dst;
     import std.algorithm.mutation : copy;
     r.copy(dst[]);
     return dst;
 }


Is there a place for part of this logic in Phobos?

I'm thinking perhaps array{N,Exactly} should be added to 
std.array.

The idea came to me after learning about dependent types in Idris:

http://www.idris-lang.org/
Oct 20 2016
parent reply Meta <jared771 gmail.com> writes:
On Thursday, 20 October 2016 at 13:05:05 UTC, Nordlöw wrote:

 On Thursday, 20 October 2016 at 12:38:40 UTC, Nordlöw wrote:

 ElementType!R[n] arrayN(size_t n, R)(R r)
 {
     assert(r.length == n);
     typeof(return) dst;
     import std.algorithm.mutation : copy;
     r.copy(dst[]);
     return dst;
 }


 Is there a place for part of this logic in Phobos?

 I'm thinking perhaps array{N,Exactly} should be added to 
 std.array.

 The idea came to me after learning about dependent types in 
 Idris:

 http://www.idris-lang.org/


There was a pull request awhile back for a small function that 
creates fixed-length arrays, but I think it was only intended to 
create them from dynamic arrays (such as `auto sarr = [1, 2, 
3].staticArray`). Personally I think it would be nice to have a 
version of `array` that creates a static array, but I don't know 
how often it would be used or what the pitfalls are, if any.
Oct 20 2016
parent ZombineDev <petar.p.kirov gmail.com> writes:
On Thursday, 20 October 2016 at 16:25:53 UTC, Meta wrote:

 On Thursday, 20 October 2016 at 13:05:05 UTC, Nordlöw wrote:

 On Thursday, 20 October 2016 at 12:38:40 UTC, Nordlöw wrote:

 ElementType!R[n] arrayN(size_t n, R)(R r)
 {
     assert(r.length == n);
     typeof(return) dst;
     import std.algorithm.mutation : copy;
     r.copy(dst[]);
     return dst;
 }


 Is there a place for part of this logic in Phobos?

 I'm thinking perhaps array{N,Exactly} should be added to 
 std.array.

 The idea came to me after learning about dependent types in 
 Idris:

 http://www.idris-lang.org/


 There was a pull request awhile back for a small function that 
 creates fixed-length arrays, but I think it was only intended 
 to create them from dynamic arrays (such as `auto sarr = [1, 2, 
 3].staticArray`). Personally I think it would be nice to have a 
 version of `array` that creates a static array, but I don't 
 know how often it would be used or what the pitfalls are, if 
 any.


I think you're talking about this PR: 
https://github.com/dlang/phobos/pull/4090. It handles range 
iteration, as well as opApply iteration.

I also think that the addition is worth having, though Andrei 
seemed to disagree. The (other?) major obstacle is safe usage, 
which currently is not enforced by the compiler, see:
https://issues.dlang.org/show_bug.cgi?id=8838
https://issues.dlang.org/show_bug.cgi?id=12625

On the bright side, it looks like one of Walter's PRs for DIP1000 
should address those issues: 
https://github.com/dlang/dmd/pull/5972/files?diff=unified#diff-33b3e2fefc5298c0b9de67897929e7ceR89
Oct 20 2016
prev sibling parent ZombineDev <petar.p.kirov gmail.com> writes:
On Thursday, 20 October 2016 at 12:38:40 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 19:39:46 UTC, Nordlöw wrote:

 On Wednesday, 19 October 2016 at 19:01:50 UTC, Meta wrote:

 https://goo.gl/t9m3YK

 I'm actually pretty impressed that this kind of code can be 
 written in D.


 Thanks! Add at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2234


 Made it even modular by factoring out arrayN at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2200

 and used at

 https://github.com/nordlow/phobos-next/blob/master/src/algorithm_ex.d#L2215

 Code:


 ElementType!R[n] arrayN(size_t n, R)(R r)
 {
     assert(r.length == n);
     typeof(return) dst;
     import std.algorithm.mutation : copy;
     r.copy(dst[]);
     return dst;
 }

 typeof(fun(E.init))[n] map(alias fun, E, size_t n)(const E[n] 
 src)
 {
     import std.algorithm.iteration : map;
     return src[].map!fun.arrayN!n;
 }

  safe pure nothrow unittest
 {
     import std.meta : AliasSeq;
     foreach (E; AliasSeq!(int, double))
     {
         enum n = 42;
         E[n] c;
         const result = map!(_ => _^^2)(c);
         static assert(c.length == result.length);
         static assert(is(typeof(result) == const(E)[n]));
     }
 }


Here's my variation on the theme. The main difference being that 
instead of eagerly evaluating the range I wrap it with additional 
static information. Unfortunately, (AFAIK) Phobos does not take 
advantage of ranges with statically known length, similarly to 
how it handles ranges with `enum bool empty = false`.

void main()
{
     import std.stdio;

     int[3] sarr = [1, 2, 3];
     auto r1 = sarr.staticLengthRange;
     static assert (isInputRange!(typeof(r1)));
     static assert (r1.length == 3);
     writeln(r1);

     auto arr = [1, 2, 3, 4];
     auto r2 = arr.map!(a => a * 2).staticLengthRange!4;
     static assert (r2.length == 4);
     writeln(r2);
}

import std.algorithm.iteration : map;
import std.range.primitives : hasLength, isInputRange;

// Note: this overload has questionable memory safety :(
// Would be quite cool if DIP1000 could support this use case
auto staticLengthRange(T, size_t n)(ref T[n] arr)
{
     return .staticLengthRange!(n, T[])(arr[]);
}

auto staticLengthRange(size_t n, R)(R range)
     if (isInputRange!R && hasLength!R)
{
     struct Result
     {
         enum size_t length = n;

         R _range;

         alias _range this;
     }

     assert (range.length == n);
     return Result(range);
}


auto staticLengthRange(size_t n, R)(R range)
     if (isInputRange!R && hasLength!R)
{
     struct Result
     {
         enum size_t length = n;

         R _range;

         alias _range this;
     }

     assert (range.length == n);
     return Result(range);
}
Oct 20 2016