Best practice of recursive variant type in C++17

1_recursive_variant_cpp17.md

Best practice of recursive variant type in C++17

Example: https://godbolt.org/z/KxY5Gz8Wx

Consider about making ADT for describing simple abstract syntax tree(AST) like below in haskell.

data Expr =  FloatLit Float |
             Symbol String |
             Let (String,Expr,Expr) |
             App (Expr,[Expr]) |
             Lambda ([String], Expr)

2_recvariant.hpp

#include <type_traits>
#include <algorithm>
#include <numeric>
#include <list>
#include <vector>
#include <variant>
#include <memory>

template <typename T>
struct Box {
  // construct from an existing object
  Box() = delete;
  Box(T rt) : t(std::make_shared<T>(std::move(rt))) {}
  template <class U>
  using enabler = std::enable_if_t<std::is_same_v<std::decay_t<U>, T>>;
  template <typename U, enabler<U>>
  Box(U&& rt) : t(std::make_shared<U>(std::forward<U>(rt))) {}
  // cast back to wrapped type
  operator T&() { return *t; }              
  operator const T&() const { return *t; }  

  T& getraw() const { return *t; }
  // store the value
  std::shared_ptr<T> t;
};

template <class... Ts>
struct overloaded : Ts... {
  using Ts::operator()...;
};
template <class... Ts>
overloaded(Ts...) -> overloaded<Ts...>;

3_ast.hpp

#include <iostream>

namespace ast{

//declare non-recursive nodes first

struct NumberLit{
 float v;
};
struct Symbol{
  std::string v;
};
// pur forward declarations for recursive nodes

struct App;
struct Let;
struct Lambda;

// declare main variant

using Expr = std::variant<NumberLit,Symbol,Box<App>,Box<Let>,Box<Lambda>>;

struct App{
  Expr callee;
  std::list<Expr> arg;
};
struct Let{
  std::string name;
  Expr expr;
  Expr newenv_expr;
};
struct Lambda{
  std::list<std::string> ids;
  Expr expr;
};

std::string toString(std::string const& s){
  return s;
}
std::string toString(float f){
 return std::to_string(f);
}
template<template<class...> class C,typename T>
std::string toStringList(C<T>const& list){
  return std::accumulate(list.cbegin(),list.cend(),T{},[](auto const& a,auto const& b)->std::string{
              return toString(a) + " " + toString(b); });
}
template<template<class...> class C,typename T>
std::string toStringList(C<Box<T>>const& list){
    C<std::string> res;
  auto c = std::transform(list.cbegin(),list.cend(),std::back_inserter(res),[](auto& a){return toString(a);});

  return std::accumulate(res.cbegin(),res.cend(),std::string{},[](auto const& a,auto const& b)->std::string{
              return a + " " + b; });
}

std::string toString(ast::Expr const& expr){
return std::visit(overloaded_rec{
      [](ast::App const& node){ return "(app " + toString(node.callee) + " " + toStringList(node.arg)+ ")";
       },
      [](ast::Let const& node){ return "(let " + node.name + " "\
                                      + toString(node.expr) + " "\
                                      + toString(node.newenv_expr)+ ")";
       },
      [](ast::Lambda const& node){ return "(lambda " + toStringList(node.ids) + " " + toString(node.expr) + ")"; },
      [](ast::NumberLit const& node){ return toString(node.v);},
      [](ast::Symbol const& node){ return node.v;}
    },expr);
}
  
}

4_test.cpp

#include "recvariant.hpp"
#include "ast.hpp"
int main(){
using namespace ast;
  auto example = Expr{
    Let{ "adder", 
         Expr{Lambda{{"x","y"}, Expr{App{Expr{Symbol{"add"}},{Expr{Symbol{"x"}},Expr{Symbol{"y"}}}}}}},
         Expr{App{Expr{Symbol{"adder"}},{Expr{NumberLit{100}},Expr{NumberLit{200}}}}}
        }};
  std::cout << ast::toString(example);
}

5. Go to HigherKind.md

metaprogramming solution with a higher kind type

template <typename Expr,typename... T>
using ExprBase = std::variant<FloatLit, 
                                IntLit, 
                                BoolLit, 
                                StringLit, 
                                Symbol, 
                                TupleLit<Expr>, 
                                StructLit<Expr>,
                                ArrayLit<Expr>, 
                                Lambda<Expr>, 
                                If<Expr>, 
                                T...>;

//because "using" cannot handle recursive type, we declare prototype as struct and make alias to it through using

struct ExprProto{
    using type = ExprBase<Box<ExprProto>>;
};
using Expr = ExprProto::type;