Преобразование дерева шаблонов выражений

Учитывая дерево шаблонов выражений, я хочу создать новое оптимизированное дерево перед его обработкой. Рассмотрим следующий пример операции умножения:

a * b * c * d,

который производит, из-за ассоциативности слева направо operator*, дерево выражений:

(((a * b) * c) * d).

Я хотел бы создать преобразованное дерево выражений, где умножение происходит справа налево:

(a * (b * (c * d))).

Рассмотрим двоичный тип выражения:

template<typename Left, typename Right>
struct BinaryTimesExpr
{
BinaryTimesExpr() = default;
BinaryTimesExpr(const BinaryTimesExpr&) = default;
BinaryTimesExpr(BinaryTimesExpr&&) = default;
BinaryTimesExpr(Left&& l, Right&& r) : left(forward<Left>(l)), right(forward<Right>(r)) {}

BinaryTimesExpr& operator=(const BinaryTimesExpr&) = default;
BinaryTimesExpr& operator=(BinaryTimesExpr&&) = default;

Left left;
Right right;
};

Определить оператор умножения operator*:

template<typename Left, typename Right>
BinaryTimesExpr<Constify<Left>, Constify<Right>> operator*(Left&& l, Right&& r)
{
return {forward<Left>(l), forward<Right>(r)};
}

где Constify определяется:

template<typename T> struct HelperConstifyRef     { using type = T;  };
template<typename T> struct HelperConstifyRef<T&> { using type = const T&; };
template<typename T>
using ConstifyRef = typename HelperConstifyRef<T>::type;

и используется для обеспечения подвыражений с константными ссылками lvalue при построении из lvalues ​​и копий (путем копирования / перемещения) значений r при построении из значений rvalue.

Определите функцию преобразования, которая создает новое дерево шаблонов выражений с предыдущими условиями:

template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
return expr;
}

template<typename Left, typename Right>
auto Transform(const BinaryTimesExpr<Left, Right>& expr) -> type(???)
{
return {(Transform(expr.left), Transform(expr.right))};
}

template<typename Left, typename Right>
auto Transform(const BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right>& expr) -> type(???)
{
return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}}); // this sintax is invalid...how can I write this?
}

Мои вопросы:

1) Как определить тип возвращаемого значения Transform функции? Я пытался использовать такие черты типа, как:

template<typename Expr>
struct HelperTransformedExpr
{
using type = Expr;
};

template<typename Left, typename Right>
struct HelperTransformedExpr<BinaryTimesExpr<Left, Right>>
{
using type = BinaryTimesExpr<typename HelperTransformedExpr<Left>::type, typename HelperTransformedExpr<Right>::type>;
};

template<typename LeftLeft, typename LeftRight, typename Right>
struct HelperTransformedExpr<BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right>>
{
using type = BinaryTimesExpr<typename HelperTransformedExpr<LeftLeft>::type,
BinaryTimesExpr<typename HelperTransformedExpr<LeftRight>::type, typename HelperTransformedExpr<Right>::type>>;
};

template<typename Expr>
using TransformedExpr = typename HelperTransformedExpr<Expr>::type;

но не знаю, как применить это, чтобы решить мой вопрос (2) ниже.

2) Как мне написать рекурсивную строку:

return Transform({Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});

3) Есть ли очиститель решение этой проблемы?

---

Редактировать: DyP представляет собой частичное решение вышеуказанной проблемы. Ниже мое полное решение на основе его ответа:

template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
return expr;
}

template<typename Left, typename Right>
auto Transform(BinaryTimesExpr<Left, Right> const& expr)
-> decltype(BinaryTimesExpr<decltype(Transform(expr.left)), decltype(Transform(expr.right))>{Transform(expr.left), Transform(expr.right)})
{
return BinaryTimesExpr<decltype(Transform(expr.left)), decltype(Transform(expr.right))>{Transform(expr.left), Transform(expr.right)};
}

template<typename LeftLeft, typename LeftRight, typename Right>
auto Transform(BinaryTimesExpr<BinaryTimesExpr<LeftLeft, LeftRight>, Right> const& expr)
-> decltype(Transform(BinaryTimesExpr<decltype(Transform(expr.left.left)), BinaryTimesExpr<decltype(Transform(expr.left.right)), decltype(Transform(expr.right))>>{Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}}))
{
return Transform(BinaryTimesExpr<decltype(Transform(expr.left.left)), BinaryTimesExpr<decltype(Transform(expr.left.right)), decltype(Transform(expr.right))>>{Transform(expr.left.left), {Transform(expr.left.right), Transform(expr.right)}});
}

int main()
{
BinaryTimesExpr<int, int> beg{1,2};
auto res = beg*3*4*5*beg;
std::cout << res << std::endl;
std::cout << Transform(res) << std::endl;
}

Выход:

(((((1*2)*3)*4)*5)*(1*2))
(1*(2*(3*(4*(5*(1*2))))))

Обратите внимание, что было необходимо применить Transform функция на каждом подвыражении, кроме самых внешних Transform позвонить (см. последний Transform перегрузки).

Полный исходный код можно найти Вот.

#include <iostream>
#include <boost/type_traits/is_same.hpp>
#include <boost/proto/proto.hpp>

namespace proto = boost::proto;
using proto::_;

struct empty {};

struct transform
: proto::reverse_fold_tree<
_
, empty()
, proto::if_<
boost::is_same<proto::_state, empty>()
, _
, proto::_make_multiplies(_, proto::_state)
>
>
{};

int main()
{
proto::literal<int> a(1), b(2), c(3), d(4);
proto::display_expr( a * b * c * d );
proto::display_expr( transform()(a * b * c * d) );
}

multiplies(
multiplies(
multiplies(
terminal(1)
, terminal(2)
)
, terminal(3)
)
, terminal(4)
)
multiplies(
terminal(1)
, multiplies(
terminal(2)
, multiplies(
terminal(3)
, terminal(4)
)
)
)

#include <iostream>

// simplified by making it an aggregate
template<typename Left, typename Right>
struct BinaryTimesExpr
{
Left left;
Right right;
};

// "debug" / demo output
template<typename Left, typename Right>
std::ostream& operator<<(std::ostream& o, BinaryTimesExpr<Left, Right> const& p)
{
o << "(" << p.left << "*" << p.right << ")";
return o;
}

// NOTE: removed reference as universal-ref yields a reference type for lvalues!
template<typename Left, typename Right>
BinaryTimesExpr < typename std::remove_reference<Left>::type,
typename std::remove_reference<Right>::type >
operator*(Left&& l, Right&& r)
{
return {std::forward<Left>(l), std::forward<Right>(r)};
}// overload to end recursion (no-op)
template<typename Expr>
auto Transform(const Expr& expr) -> Expr
{
return expr;
}

template<typename LeftLeft, typename LeftRight, typename Right>
auto Transform(BinaryTimesExpr < BinaryTimesExpr<LeftLeft, LeftRight>,
Right > const& expr)
-> decltype(Transform(
BinaryTimesExpr < LeftLeft,
BinaryTimesExpr<LeftRight, Right>
> {expr.left.left, {expr.left.right, expr.right}}
))
{
return Transform(
BinaryTimesExpr < LeftLeft,
BinaryTimesExpr<LeftRight, Right>
> {expr.left.left, {expr.left.right, expr.right}}
);
}int main()
{
BinaryTimesExpr<int, int> beg{1,2};
auto res = beg*3*4*5*6;
std::cout << res << std::endl;
std::cout << Transform(res) << std::endl;
}