In pstl/include/pstl/internal/execution_impl.h these function templates are defined:

template <typename _Tp>
std::false_type __lazy_and(_Tp, std::false_type)
{
    return std::false_type{};
};

template <typename _Tp>
inline _Tp
__lazy_and(_Tp __a, std::true_type)
{
    return __a;
}

(There are also __lazy_or function template which seem to be completely unused).

It gets used in code like this:

template <typename _ExecutionPolicy, typename... _IteratorTypes>
auto
__is_vectorization_preferred(_ExecutionPolicy&& __exec)
    -> decltype(__internal::__lazy_and(__exec.__allow_vector(),
                                       typename __internal::__is_random_access_iterator<_IteratorTypes...>::type()))
{
    return __internal::__lazy_and(__exec.__allow_vector(),
                                  typename __internal::__is_random_access_iterator<_IteratorTypes...>::type());
}


Where __allow_vector is a specialization of a relatively inexpensive class template, and __is_random_access_iterator is a recursive class template:


template <typename _IteratorType, typename... _OtherIteratorTypes>
struct __is_random_access_iterator
{
    static constexpr bool value = __internal::__is_random_access_iterator<_IteratorType>::value &&
                                  __internal::__is_random_access_iterator<_OtherIteratorTypes...>::value;
    typedef std::integral_constant<bool, value> type;
};

template <typename _IteratorType>
struct __is_random_access_iterator<_IteratorType>
    : std::is_same<typename std::iterator_traits<_IteratorType>::iterator_category, std::random_access_iterator_tag>
{
};


Unless I'm mistaken, the only thing that is lazy here is the instantiation of __allow_vector::value, which is cheap anyway.

In order to choose an overload of __lazy_and the second argument needs to be complete, which instantiates __is_random_access_iterator<_IteratorTypes...>::type which requires the instantiation of __is_random_access_iterator<_IteratorTypes...>::value, which is VERY UN-LAZY. It requires instantiating __is_random_access_iterator for every element of the pack, even if the first element is not a random access iterator.

A better implementation of __is_random_access_iterator would be:

template <typename _IteratorType, typename... _OtherIteratorTypes>
struct __is_random_access_iterator;

template <typename _IteratorType>
struct __is_random_access_iterator<_IteratorType>
    : std::is_same<typename std::iterator_traits<_IteratorType>::iterator_category, std::random_access_iterator_tag>
{
};

template <typename _IteratorType, typename... _OtherIteratorTypes>
struct __is_random_access_iterator
    : std::conjunction<__is_random_access_iterator<_IteratorType>,
                       __is_random_access_iterator<_OtherIteratorTypes>...>::type
{
};

Personally I'd get rid of __lazy_and completely, make __is_random_access_iterator non-variadic, and write the functions using it like this (assuming bug 47601 gets fixed so the __alow_vector alias template works):

template <typename _ExecutionPolicy, typename... _IteratorTypes>
typename std::conjunction<__allow_vector<_ExecutionPolicy>,
           __is_random_access_iterator<_IteratorTypes>...>::type
__is_vectorization_preferred(_ExecutionPolicy&&)
{
    return {};
}


This is actually lazy. It never instantiates any __is_random_access_iterator specialization if the __allow_vector trait is false, and only instantiates as many as needed to determine the answer.

(N.B. the __exec parameter is redundant, since the _ExecutionPolicy type has to be given explicitly anyway, and that already provides all the information required, but changing that would require changes to every caller).