static map as a type function

Paul Backus snarwin at
Thu Sep 24 03:51:55 UTC 2020

On Thursday, 24 September 2020 at 03:17:44 UTC, Steven 
Schveighoffer wrote:
> The recursive version is not nice code. It's hard to understand 
> and difficult to follow. It's main advantage is that because 
> it's essentially a functional language, and all templates are 
> cached, in certain cases, you can see a performance gain 
> because the compiler can avoid actually redoing what it did. In 
> practice, for things like staticMap, this doesn't ever pan out.
> I don't see how you solve the tail recursion thing anyway -- 
> each template instance cannot rely on the work that has already 
> been done, because of static if.
> The static map type function is a loop over an array. Easy to 
> understand, easy to write. It's actually boring code. Static 
> map shouldn't be interesting code at all.
> -Steve

I feel the same way about the naive recursive version:

template staticMap!(alias F, Args...) {
     static if (Args.length == 0)
         alias staticMap = AliasSeq!();
         alias staticMap = AliasSeq!(F!(Args[0]), staticMap!(F, 
Args[1 .. $]));

One base case, one recursive case, one line for each. The code 
practically writes itself. How could it be any clearer or more 

Making it tail-recursive takes away some of the elegance, but 
doesn't make it any more "interesting":

template staticMap(alias F, Args...) {
     template loop(size_t i, Args...) {
         static if (start == Args.length)
             alias loop = Args;
             alias loop = loop!(i + 1, Args[0 .. i], F!(Args[i]), 
Args[i+1 .. $]);
     alias staticMap = loop!(0, Args);

If you have spent any time at all writing code in a functional 
language with tail-call elimination, this pattern will be 
immediately familiar to you. There's nothing about it that's hard 
to understand, or difficult to follow. It's completely textbook.

Of course, for someone who lacks that background, it might very 
well look bewildering--in the same way that, say, the Visitor 
pattern might look bewildering to someone unfamiliar with the 
idioms of OOP. Does that mean it's a bad pattern? Or does it just 
mean it's a pattern they haven't learned yet?

More information about the Digitalmars-d mailing list