www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Auto recursive function

reply Razvan Nitu <razvan.nitu1305 gmail.com> writes:
Hi,

I am currently trying to create a function 
makeMultidimensionalArray which allocates memory for a 
multidimensional array. It is very similar with [1],
the difference being that it is uninitialized. Here is the code:

auto makeMultidimensionalArray(T, Allocator)(auto ref Allocator 
alloc, size_t[] lengths)
{
     if (lengths.length == 1)
     {
         return makeArray!T(alloc, lengths[0]);
     }
     else
     {
         alias E = typeof(makeMultidimensionalArray!T(alloc, 
lengths[1..$]));
         auto ret = makeArray!E(alloc, lengths[0]);
         foreach (ref e; ret)
             e = makeMultidimensionalArray!T(alloc, lengths[1..$]);
         return ret;
     }
}

The lengths[] specifies the lengths for each dimension. The 
problem with this code is that auto is going to be evaluated to 
T[] for the first time and when it
recurs, creating T[][] I get the error "mismatched function 
return type inference of T[][] and T[]". Is there a way to 
surpass that? I saw that in [1]
the recursive call is done by prefixing the function name with a 
'.'; I tried that but it doesn't work. I must be missing 
something, any ideas?

Thanks,
RazvanN

[1] 
https://github.com/dlang/phobos/blob/master/std/experimental/ndslice/slice.d#L834
Jan 11
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu wrote:
 Hi,

 I am currently trying to create a function 
 makeMultidimensionalArray which allocates memory for a 
 multidimensional array. It is very similar with [1],
 the difference being that it is uninitialized. Here is the code:

 [...]
I believe you should not do this with recursion. Because that'll instantiate the template multiple times with different types. What is wrong with using ndslice here ?
Jan 11
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/11/2017 11:30 AM, Stefan Koch wrote:
 On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu wrote:
 Hi,

 I am currently trying to create a function makeMultidimensionalArray
 which allocates memory for a multidimensional array. It is very
 similar with [1],
 the difference being that it is uninitialized. Here is the code:

 [...]
I believe you should not do this with recursion. Because that'll instantiate the template multiple times with different types. What is wrong with using ndslice here ?
Agreed but the question is still valid. I had similar cases before where std.range.choose looked like a solution but did not work. Here's my current attempt, which fails: import std.stdio; import std.experimental.allocator.gc_allocator; import std.experimental.allocator; auto one(T, Allocator)(auto ref Allocator alloc, size_t length) { return makeArray!T(alloc, length); } auto two(T, Allocator)(auto ref Allocator alloc, size_t[] lengths) { // Error: forward reference to inferred return type of function call 'makeMultidimensionalArray!int(alloc, lengths[1..__dollar])' alias E = typeof(makeMultidimensionalArray!T(alloc, lengths[1..$])); auto ret = makeArray!E(alloc, lengths[0]); foreach (ref e; ret) e = makeMultidimensionalArray!T(alloc, lengths[1..$]); return ret; } auto makeMultidimensionalArray(T, Allocator)(auto ref Allocator alloc, size_t[] lengths) { import std.range: choose; return choose(lengths.length == 1, one!T(alloc, lengths[0]), two!T(alloc, lengths)); } void main() { writeln(makeMultidimensionalArray!int(GCAllocator.instance, [3, 4])); } Ali
Jan 11
parent Martin Nowak <code dawg.eu> writes:
On Wednesday, 11 January 2017 at 19:39:17 UTC, Ali Çehreli wrote:
     return choose(lengths.length == 1, one!T(alloc, 
 lengths[0]), two!T(alloc, lengths));
Well, choose is the right tool when the choice can only be made at runtime. That would be uncommon for dimensionality. Anyhow mentioning ndslice for multi-dim seems like the sanest tip here. https://github.com/libmir/mir
Jan 11
prev sibling parent Razvan Nitu <razvan.nitu1305 gmail.com> writes:
On Wednesday, 11 January 2017 at 19:30:05 UTC, Stefan Koch wrote:
 On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu 
 wrote:
 Hi,

 I am currently trying to create a function 
 makeMultidimensionalArray which allocates memory for a 
 multidimensional array. It is very similar with [1],
 the difference being that it is uninitialized. Here is the 
 code:

 [...]
I believe you should not do this with recursion. Because that'll instantiate the template multiple times with different types. What is wrong with using ndslice here ?
Maybe you want to allocate memory for more complex data structures; Using the function I am implementing, you will have the multidimensional array initialized with the default values; you don't have to pass a slice from which the initialization data is taken.
Jan 11
prev sibling next sibling parent Martin Nowak <code dawg.eu> writes:
On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu wrote:
 auto makeMultidimensionalArray(T, Allocator)(auto ref Allocator 
 alloc, size_t[] lengths)
 {
     if (lengths.length == 1)
Looks like `static if` would fix your specific problem.
Jan 11
prev sibling next sibling parent Ignacious <I.D.T ProjectMaya.com> writes:
On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu wrote:
 Hi,

 I am currently trying to create a function 
 makeMultidimensionalArray which allocates memory for a 
 multidimensional array. It is very similar with [1],
 the difference being that it is uninitialized. Here is the code:

 auto makeMultidimensionalArray(T, Allocator)(auto ref Allocator 
 alloc, size_t[] lengths)
 {
     if (lengths.length == 1)
     {
         return makeArray!T(alloc, lengths[0]);
     }
     else
     {
         alias E = typeof(makeMultidimensionalArray!T(alloc, 
 lengths[1..$]));
         auto ret = makeArray!E(alloc, lengths[0]);
         foreach (ref e; ret)
             e = makeMultidimensionalArray!T(alloc, 
 lengths[1..$]);
         return ret;
     }
 }

 The lengths[] specifies the lengths for each dimension. The 
 problem with this code is that auto is going to be evaluated to 
 T[] for the first time and when it
 recurs, creating T[][] I get the error "mismatched function 
 return type inference of T[][] and T[]". Is there a way to 
 surpass that? I saw that in [1]
 the recursive call is done by prefixing the function name with 
 a '.'; I tried that but it doesn't work. I must be missing 
 something, any ideas?

 Thanks,
 RazvanN

 [1] 
 https://github.com/dlang/phobos/blob/master/std/experimental/ndslice/slice.d#L834
This is probably not possible. You are trying to have multiple return types for the same function. You are thinking that each recursive call is a new template but that doesn't seem to be the case. Instead, maybe try using string mixins to generate the allocations. Should be quite easy and will work. You could also try to use a helper function that you pass the fully declared array(all dimensions) and the helper function then allocates each dimension recursively... The difference is that you are not passing around/returning sub-arrays so you don't have to worry about type mismatches.
Jan 11
prev sibling next sibling parent reply Ignacious <I.D.T ProjectMaya.com> writes:
On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu wrote:
 Hi,

 I am currently trying to create a function 
 makeMultidimensionalArray which allocates memory for a 
 multidimensional array. It is very similar with [1],
 the difference being that it is uninitialized. Here is the code:

 auto makeMultidimensionalArray(T, Allocator)(auto ref Allocator 
 alloc, size_t[] lengths)
 {
     if (lengths.length == 1)
     {
         return makeArray!T(alloc, lengths[0]);
     }
     else
     {
         alias E = typeof(makeMultidimensionalArray!T(alloc, 
 lengths[1..$]));
         auto ret = makeArray!E(alloc, lengths[0]);
         foreach (ref e; ret)
             e = makeMultidimensionalArray!T(alloc, 
 lengths[1..$]);
         return ret;
     }
 }

 The lengths[] specifies the lengths for each dimension. The 
 problem with this code is that auto is going to be evaluated to 
 T[] for the first time and when it
 recurs, creating T[][] I get the error "mismatched function 
 return type inference of T[][] and T[]". Is there a way to 
 surpass that? I saw that in [1]
 the recursive call is done by prefixing the function name with 
 a '.'; I tried that but it doesn't work. I must be missing 
 something, any ideas?

 Thanks,
 RazvanN

 [1] 
 https://github.com/dlang/phobos/blob/master/std/experimental/ndslice/slice.d#L834
If you change the return type to a void* your code basically works. void* makeMultidimensionalArray(T, Allocator)(auto ref Allocator alloc, size_t[] lengths) { if (lengths.length == 1) { int x = 0x01FEEF01; return cast(void*)makeArray!T(alloc, lengths[0], x); } else { alias E = typeof(makeMultidimensionalArray!T(alloc, lengths[1..$])); auto ret = makeArray!E(alloc, lengths[0]); foreach (ref e; ret) e = makeMultidimensionalArray!T(alloc, lengths[1..$]); return cast(void*)ret; } } The problem is that then you need to cast back and that essentially results in the original problem. Can be done but probably gonna have to use string mixins.
Jan 11
parent Bauss <jj_1337 live.dk> writes:
On Thursday, 12 January 2017 at 00:30:33 UTC, Ignacious wrote:
 On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu 
 wrote:
 [...]
If you change the return type to a void* your code basically works. void* makeMultidimensionalArray(T, Allocator)(auto ref Allocator alloc, size_t[] lengths) { if (lengths.length == 1) { int x = 0x01FEEF01; return cast(void*)makeArray!T(alloc, lengths[0], x); } else { alias E = typeof(makeMultidimensionalArray!T(alloc, lengths[1..$])); auto ret = makeArray!E(alloc, lengths[0]); foreach (ref e; ret) e = makeMultidimensionalArray!T(alloc, lengths[1..$]); return cast(void*)ret; } } The problem is that then you need to cast back and that essentially results in the original problem. Can be done but probably gonna have to use string mixins.
That isn't a solution and will probably introduce other bugs. As soon as you have to result to using void* is an indication of bad design IMO, because it leads to very unsafe possibilities.
Jan 12
prev sibling parent thedeemon <dlang thedeemon.com> writes:
On Wednesday, 11 January 2017 at 19:23:10 UTC, Razvan Nitu wrote:
 Hi,

 I am currently trying to create a function 
 makeMultidimensionalArray which allocates memory for a 
 multidimensional array.
You were very close to the answer: auto makeMultidimensionalArray(int N, T, Allocator)(auto ref Allocator alloc, size_t[N] lengths) { static if (lengths.length == 1) { return makeArray!T(alloc, lengths[0]); } else { alias E = typeof(makeMultidimensionalArray!(N-1,T)(alloc, lengths[1..$])); auto ret = makeArray!E(alloc, lengths[0]); foreach (ref e; ret) e = makeMultidimensionalArray!(N-1, T)(alloc, lengths[1..$]); return ret; } } The key point is that return type depends on length of "lengths" array (dimensionality), so if this length is only known at runtime this is a dependent type, something D lacks (you'll need Idris or Agda for those). In D return type must be known at compile time and hence the length of "lengths" must be a compile time argument. With such argument everything compiles smoothly.
Jan 12