C++ simple template recursion

Question

I'm pretty sure the solution to the following problem is quite standard but I couldn't find the right terms to search for it. I've two classes, say, SomeB<A> and SomeA<B>. I want to create an instance of SomeB<A> where A:=SomeA<B> and B:=SomeB<A>. The (simplified) code looks like:

template<typename A>
class SomeB
{
    A getA() { /* ... */ }
};

template<typename B>
class SomeA
{
    B getB() { /* ... */ }
};

int main(int argc, char **argv)
{
    SomeA<SomeB<SomeA<SomeB<...> > > > test;
    //                       /\
    //                        |
    //                        +---- recursion
    test.getB();
    return 0;
}

Now, how do I tell the compiler that there no "suprises" like in SomeA<SomeB<SomeA<SomeB<Suprise_AnotherA<...>>>>>?

Sorry, but directly recursive types cannot be defined in C++. — Deduplicator, Sep 22 '14 at 16:50

score 1 · Accepted Answer · answered Sep 22 '14 at 17:24

1

Thanks to Vittorio Romeo for pointing me to template template parameters. This one compiles and works:

template<template<typename> class A>
class SomeB
{
public:
    A<SomeB> getA() { return A<SomeB>(); }
};

template<typename B>
class SomeA
{
public:
    B getB() { return B(); }
};

int main(int argc, char **argv)
{
    SomeB<SomeA> test;
    test.getA();
    return 0;
}

Meta information for those who are curious: SomeB is a tree (node) class and SomeA is a class that finds a specific child of a node in the tree. SomeA can be implemented in many different ways and it may use its own data structure to store children, i.e., instances of SomeB, for efficient filtering.

answered Sep 22 '14 at 17:24

conner82

41
4

1

I'm sorry, but I doesn't look like the thing you've described in the question. I mean `SomeA` in the `SomeB test;` is a template. It is not of the type `SomeA` as you intended. – Kostya Sep 22 '14 at 18:06
@Kostya: Touché! I'm pretty sure it solves my problem, though. If I had known template template parameters, I would've asked the question differently. I'm sure there's an xkcd about this... – conner82 Sep 22 '14 at 18:49

score 0 · Answer 2 · answered Sep 22 '14 at 19:19

Lets change a rather clumsy C++ notation to a more type-theoretic(ish)one, so that we could try to clearly define what you want.

template<typename A> class SomeB { ... };

Actually means that you have a thingy named SomeB that takes in a simple type and returns another simple type:

SomeB : typename -> typename

And, for example, if you have the "template template parameter" thing like that:

template<template<typename> class A> class SomeB { ... };

Then that would translate into this:

SomeB : (typename -> typename) -> typename

Now here is how I understood what you want. You say "I have this two guys here"

SomeA : typename -> typename
SomeB : typename -> typename

"If I wanted to apply like SomeA<SomeB> that'd be illegal since SomeB is not a typename -- it is typename->typename. If only could I apply that SomeB to something to get a simple type...

Oh! How about I apply it like SomeB<SomeA>? No, that'd be illegal since SomeB is not a typename -- it is typename->typename. If only could I apply that SomeA to something to get a simple type...

Oh! How about I apply it like SomeA<SomeB>? No, that'd be illegal since SomeA is not a typename -- it is typename->typename. If only could I apply that SomeB to something to get a simple type...

Oh! How about I apply it like SomeB<SomeA>? No, that'd be illegal since SomeA is not a typename -- it is typename->typename. If only could I apply that SomeB to something to get a simple type..."

And so on -- You got the idea. And that is very similar to all classical logical paradoxes like the liar paradox. More formally, what you want to do is called an impredicative definition.

And guess what? Type theory was invented by Bertrand Russel exactly to destroy impredicativity.

So your intention is not just conflicts with ones ability to express himself using C++, it is in a conflict with the basic ideas of the type theory. And, to my taste, doesn't make any sense at all. Like the liar paradox.

C++ simple template recursion

2 Answers2