What is struct NIL { typedef NIL Head; }?

Question

I am reading about template metaprogramming. I could not understand what these lines mean; the following code concerns about doing metaprogramming on a linked list.

struct NIL {
typedef NIL Head;
typedef NIL Tail;
};

template <typename H, typename T=NIL> struct Lst {
    typedef H Head;
    typedef T Tail;
};

template <int N> struct Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

The above is coming from https://monoinfinito.wordpress.com/series/introduction-to-c-template-metaprogramming/ . I would greatly appreciate any guidance as to what it means to have struct NIL, which has typedef NIL Head, and typedef NIL Tail. Nil is a type, sure, but if I have typedef NIL Head, for example, does it mean i have another recursive Head and Tail within each Head?

Answer 1

No, typedef NIL Head; doesn't mean you have a NIL within each NIL.

It simply means NIL::Head is another name for NIL. Ditto for NIL::Tail.

This does mean you can write the types recursively, for example NIL::Head::Tail::Tail::Tail::Head::Head is also a name for NIL. However there's no actual recursive type here.

Answer 2

NIL is just another name for nothing.

It isn't NULL because that was taken.

Here, we are creating a LISP like linked list of "head" and "tail". To represent the end of the list, place a NIL.

NIL satisfies the layout of a list, but one with both head and tail being NIL. Myself I'd be tempted to have written:

struct NIL;

template <typename H, typename T=NIL> struct Lst {
  typedef H Head;
  typedef T Tail;
};

struct NIL:Lst{};

to make NIL as the name of the empty list more clear.

By making NIL have head & tail, some template metaprogramming becomes easier (and some becomes harder). The fact that they are the same type does mean that in one sense the NIL list has an infinite length; but in another sense it has zero length, as we define length to be the distance until we reach NIL.

typedefs are not "within" the type, they are defined inside like how data members are. They are more like pointers than members. In non template metaprogramming:

struct node {
  node* head, *tail;
};
struct NIL:node{
  NIL() : node{this, this} {}
};