How to avoid unnecessary instantiations with Boost.MP11

Question

I have been using my own TMP library for quite some time. However, I want to start using Boost.MP11. The interface is quite nice, and, to give myself some motivation to learn it, I did the 2022 Advent of Code as much as I could at compile time, using Boost.MP11.

However, there were some things that I had to do, which I did not like. I went back to clean some things up, and one place where I am still a bit confused, is how to prevent unnecessary instantiations. I'm sure some use of mp_valid is the way to go, but I could use some guidance.

For example, consider the following implementation of push_heap, using Boost.MP11 (which I implemented as part of implementing Dijkstra's algorithm for one of the challenges).

It is a bit verbose in order to make it obvious what I want to achieve, namely the instantiation of templates only when they are true.

I must be misunderstanding something about Boost.MP11, so I would like to see an elegant Boost.MP11 implementation of push_heap.

template <typename IndexT>
using parent = mp_constant<(IndexT::value - 1) / 2>;

template <typename ListT, typename IndexT> struct BubbleUp;

template <
    typename ListT,
    typename IndexT,
    typename CondT = mp_less<
        mp_at<ListT, parent<IndexT>>,
        mp_at<ListT, IndexT>>>
struct BubbleUpImpl
: BubbleUp<
    mp_replace_at<
        mp_replace_at<ListT, IndexT, mp_at<ListT, parent<IndexT>>>,
        parent<IndexT>,
        mp_at<ListT, IndexT>>,
    parent<IndexT>>
{ };
template <typename ListT, typename IndexT>
struct BubbleUpImpl<ListT, IndexT, mp_false>
{
    using type = ListT;
};

template <typename ListT, typename IndexT>
struct BubbleUp
: BubbleUpImpl<ListT, IndexT>
{ };
template <typename ListT>
struct BubbleUp<ListT, mp_size_t<0>>
{
    using type = ListT;
};

// Not same as std::push_heap - it pushes and heapifies
template <typename ListT, typename T>
using push_heap = typename BubbleUp<
    mp_push_back<ListT, T>,
    mp_size<ListT>>::type;

---

EDIT

Here is my attempt with Boost.MP11, but I am less than enamored with it, and still searching for a better alternative, and especially interested in learning how best to do these kinds of things with Boost.MP11. Note that the semantics here are the same as std::push_heap - the difference above was to try and simplify.

namespace heap_detail {

template <typename ListT, typename Index1T, typename Index2T>
using swap_at = mp_replace_at<
    mp_replace_at<ListT, Index1T, mp_at<ListT, Index2T>>,
    Index2T,
    mp_at<ListT, Index1T>>;

template <typename CmpQ>
class PushHeap
{
    template <typename T>
    using heap = mp_first<T>;

    template <typename T>
    using child = mp_second<T>;

    template <typename T>
    using parent = mp_if<
        mp_less<mp_size_t<0>, child<T>>,
        mp_constant<(child<T>::value - 1) / 2>>;

    template <typename T>
    using bubble_up = mp_list<
        mp_if<
            mp_invoke_q<
                CmpQ,
                mp_at<heap<T>, parent<T>>,
                mp_at<heap<T>, child<T>>>,
            swap_at<heap<T>, parent<T>, child<T>>>,
        parent<T>>;

public:
    template <typename ListT>
    using fn = mp_back<mp_iterate<
        mp_list<ListT, mp_minus<mp_size<ListT>, mp_int<1>>>,
        mp_first,
        bubble_up>>;
};
} // namespace heap_detail

template <typename ListT, typename CmpQ>
using push_heap_q = mp_invoke_q<heap_detail::PushHeap<CmpQ>, ListT>;

template <typename ListT, template <typename...> class Cmp = mp_less>
using push_heap = push_heap_q<ListT, mp_quote<Cmp>>;

Also, for what it's worth, here is the rest of the heap interface. Maybe these will show more opportunity for learning how better to use Boost.MP11.

make_heap

template <typename ListT, typename CmpQ>
using make_heap_q = mp_fold_q<
    ListT,
    mp_list<>,
    mp_compose_q<mp_quote<mp_push_back>, mp_bind_back<push_heap_q, CmpQ>>>;

template <typename ListT, template <typename...> class Cmp = mp_less>
using make_heap = make_heap_q<ListT, mp_quote<Cmp>>;

And something to push additional items onto the heap

template <typename ListT, typename CmpQ, typename... Ts>
using heap_push_back_q = mp_fold_q<
    mp_list<Ts...>,
    ListT,
    mp_compose_q<mp_quote<mp_push_back>, mp_bind_back<push_heap_q, CmpQ>>>;

And pop_heap, which seems way overly complicated - specialization seems much easier to read and write, so, I believe I am missing something fundamental with Boost.MP11.

template <typename CmpQ>
class PopHeap
{
    template <typename T>
    using heap = mp_first<T>;

    template <typename T>
    using parent = mp_second<T>;

    template <typename T>
    using left_child = mp_constant<parent<T>::value * 2 + 1>;

    template <typename T>
    using right_child = mp_constant<parent<T>::value * 2 + 2>;

    template <typename T>
    using child_to_swap = mp_eval_or_q<
        left_child<T>,
        mp_quote<mp_if>,
        mp_invoke_q<
            CmpQ,
            mp_at<heap<T>, left_child<T>>,
            mp_at<heap<T>, right_child<T>>>,
        right_child<T>,
        left_child<T>>;

    template <typename T>
    using bubble_down = mp_list<
        mp_if<
            mp_invoke_q<
                CmpQ,
                mp_at<heap<T>, parent<T>>,
                mp_at<heap<T>, child_to_swap<T>>>,
            swap_at<heap<T>, parent<T>, child_to_swap<T>>>,
        child_to_swap<T>>;

public:
    template <typename ListT>
    using fn = mp_push_back<
        mp_back<
            mp_iterate<
                mp_list<
                    mp_rotate_right<mp_pop_front<ListT>, mp_int<1>>,
                    mp_size_t<0>>,
                mp_first,
                bubble_down>>,
        mp_first<ListT>>;
};

template <typename ListT, typename CmpQ>
using pop_heap_q = mp_invoke_q<heap_detail::PopHeap<CmpQ>, ListT>;

template <typename ListT, template <typename...> class Cmp = mp_less>
using pop_heap = pop_heap_q<ListT, mp_quote<Cmp>>;