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