Failure of recursive template instantiation

Question

I've been working on a basic typelist lately, however, I am facing some trouble with my is_sorted() implementation. Here is an excerpt from my code:

https://code.sololearn.com/cmrHf83vpeK6/?ref=app

My idea was to continuously compare the second and first element while removing the head, until either the comparison returns true or the typelist is empty. Since that doesn't work for a typelist with a single element, I included a check via std::conditional meant to jump directly to the base case if only one element remains, since such a typelist would be sorted automatically.
However, it seems that the instantiation nonetheless arrives at a point where cs::front is instantiated for an empty typelist, resulting in the error one can see when uncommenting one of the print statements in main().
I can't seem to make out where/ why this happens, so if someone could explain that to me, I would appreciate it a lot. Of course, if there is a better approach to the problem, I would like to hear about it as well.

Answer 1

The problem is that both true and false branches of std::conditional have to be correct, even if that path is not chosen in the actual program.

template argument substitution happens outside std::conditional.

std::conditional_t<
is_empty_v< pop_front_t< List > >,

is_sorted_implementation< pop_front_t< List >, Compare, false >,
is_sorted_implementation< pop_front_t< List >, Compare, Compare< front_t< pop_front_t< List > >, front_t< List > >::value >

is_sorted_v< typelist< int >, less > is evaluated to:

std::conditional_t<
true,

is_sorted_implementation< typelist<>, Compare, false >,
is_sorted_implementation< typelist<>, Compare, Compare< front_t< typelist<> >, front_t< typelist<int> > >::value >

and no specialization exists for front_t< typelist<> > so it fails to compile.

You can't really make a specialization for it either because what is type going to be?
template < >
struct front< typelist< > >
{
using type = ???;
};

If you don't want my solution then just ignore the part below "----"

Btw, you can just inherit from std::false_type or true_type instead of doing static constexpr bool value{ false };

---------
I don't really know the answer myself, I'm no template expert but I solved it by just adding another bool to the is_sorted_implementation template like this:

template < typename List, template < typename T1, typename T2 > typename Compare, bool Accumulator = false, bool Empty = is_empty_v< List >, bool LastOne = is_empty_v< pop_front_t<List>> >
struct is_sorted_implementation;

and changed your class with the std::conditional to:
template < typename List, template < typename T1, typename T2 > typename Compare >
struct is_sorted_implementation< List, Compare, false, false, false > : is_sorted_implementation< pop_front_t< List >, Compare, Compare< front_t< pop_front_t< List > >, front_t< List > >::value, false, is_empty_v< pop_front_t<List>> >
{};

and then added a few more specializations for when LastOne is true/false.

Answer 2

Thanks for the detailed answer, Dennis. I figured the same a little while earlier prior to seeing your answer and solved it in a slightly different way. By adding another level of indirection, you can defer the evaluation of the type arguments given to std::conditional until after one has been selected. Therefore, I wrapped the first argument in an identity template, and introduced a new template to wrap the second part:

template < typename List, template < typename T1, typename T2 > typename Compare >
struct is_sorted_evaluation
{
using type = is_sorted_implementation< pop_front_t< List >, Compare, Compare< front_t< pop_front_t< List > >, front_t< List > >::value >;
}

As a consequence, std::conditional only selects the type function instance, which is later evaluated by ::type after the call itself. But I also like the approach with another parameter, not sure which I'll end up choosing.

I actually did something similar for my sort() implementation, so I'm feeling a little dumb right now, heh.