Type switch for Algebrical Data Types in C++11
This is a short post to complete the discussion on Algebrical Data Types in C++11.
An important point for the adoption of Algebrical Data Types (ADTs) is the possibility to perform a select operation based on the active type in an ADT variable. While the use of a class with overloaded function members is practical it is not as clean as it should, in particular if compared with languages with native ADTs.
The syntax in Haskell is:
The implementation of the above is straightforward, and reduces to a variadic member function that iterates over the arguments, extracts the index associated with the first argument type using bytype, and then at run-time invokes the index corresponding the the current state of the ADT. When no lambda matches it generates an exception.
The non-straightforward part is the template that extracts the return type and the type of the first argument from a lambda expression. The use of std::function would have made select less elegant and less efficient.
It has to be noted that in C++11 a lambda expression has a special type called closure type that "is an unique unnamed non-union non-aggregate type" (cppref).
The following is the recursive pattern typical of variadic template parameters:
template <typename F, typename... FArgs>
Then the typedef named signature extracts the function signature of the lambda expression by taking the address of the operator() of the lambda closure type. Finally the extractfx is an helper function that returns the first argument type and the return type of a function signature.
The lambdalist template allows to extract the result type from a list of lambda expressions. At the moment it just returns the first return type. Internally lambdalist uses the same scheme of signature and extractfx.
An important point for the adoption of Algebrical Data Types (ADTs) is the possibility to perform a select operation based on the active type in an ADT variable. While the use of a class with overloaded function members is practical it is not as clean as it should, in particular if compared with languages with native ADTs.
The syntax in Haskell is:
depth :: Tree -> Int depth Empty = 0 depth (Leaf n) = 1 depth (Node l r) = 1 + max (depth l) (depth r)
In particular we would like to easily express it in C++ as follows:sumtype<int,std::string> adt(10); std::cout << adt.select( [a] (int x) return (int)10+a; }, [] (std::string w) { return (int)20; } );
The select function receives a list of lambda expressions and, at run-time invokes the one whose first argument type matches the active type in the ADT. Thanks to the direct use of lambda expressions everything is inlined by the compiler.The implementation of the above is straightforward, and reduces to a variadic member function that iterates over the arguments, extracts the index associated with the first argument type using bytype
The non-straightforward part is the template that extracts the return type and the type of the first argument from a lambda expression. The use of std::function would have made select less elegant and less efficient.
It has to be noted that in C++11 a lambda expression has a special type called closure type that "is an unique unnamed non-union non-aggregate type" (cppref).
The following is the recursive pattern typical of variadic template parameters:
template <typename F, typename... FArgs>
auto select(F x, FArgs... fx) -> typename lambdalist<F>::result { typedef typename function_traits<decltype(&F::operator())>::signature signature; typedef typename extractfx<signature>::first first; if(bytype<first>::index == _index) return x(*(first*)value);
else return select(fx...); }
The lambdalist
Conclusions
The code on github has been updated with new pattern.
The proposed approach can be extended with some compile time verifications that improve the robustness of the paradigm: the set of types of the argument of the lambdas should be equivalent of the set of the ADT. This means no duplicates, and no missing types.
Comments