type variables

[Stefan Koch]

On Sunday, 2 August 2020 at 15:04:07 UTC, Paul Backus wrote:
> On Sunday, 2 August 2020 at 12:31:00 UTC, Stefan Koch wrote:
>> Take this for example.
>> int[] iota(int start, int finish)
>> {
>>     int[] result = [];
>>     result.length = finish - start;
>>     foreach(i;start .. finish)
>>     {
>>         result[i - start] = i;
>>     }
>>     return result;
>> }
>>
>> Whereas the recursive function for this,
>> is something I do not even want to put on here.
>> Because it's way to complicated for this simple task.
>
> In fact, the naive recursive version of iota is actually even 
> simpler:
>
> int[] iota(int start, int finish)
> {
>     if (start > finish)
>         return [];
>     else
>         return [start] ~ iota(start + 1, finish);
> }
>
> Again, the problem with this function is not complexity or 
> readability, but performance. It performs many unnecessary 
> memory allocations, and consumes (finish - start) stack frames 
> instead of 1.

How is that easier?

It requires you to have a stack, which also means that you have 
to keep track of the stack frames in order to execute this in 
your head.
this particular function allocates N literals array + and does N 
concatenations.
Which when naively implemented consumes N*N + 2N words of memory.