On the Boost mailinglist, the following clever trick to create a tuple-like entity was recently posted by @LouisDionne:
#include <iostream> auto list = [](auto ...xs) { return [=](auto access) { return access(xs...); }; }; auto length = [](auto xs) { return xs([](auto ...z) { return sizeof...(z); }); }; int main() { std::cout << length(list(1, '2', "3")); // 3 }
Live Example.
The cleverness is that list
is a lambda taking a variadic parameter-list as input, and returning a lambda as an output that will take another lambda to act on its input. Similarly, length
is a lambda taking a list-like entity, to which it will supply the variadic sizeof...
operator to the list's original input parameters. The sizeof...
operator is wrapped inside a lambda so that it can be passed to the list
.
Question: is there a name for this tuple-creation idiom? Perhaps from a functional programming language where higher-order functions are more commonly used.
In mathematics, a tuple is a finite ordered list (sequence) of elements. An n-tuple is a sequence (or ordered list) of n elements, where n is a non-negative integer. There is only one 0-tuple, referred to as the empty tuple. An n-tuple is defined inductively using the construction of an ordered pair.
Tuples are used to store multiple items in a single variable. Tuple is one of 4 built-in data types in Python used to store collections of data, the other 3 are List, Set, and Dictionary, all with different qualities and usage. A tuple is a collection which is ordered and unchangeable.
A tuple is essentially an immutable (can't be changed in-place in memory) list. Named tuples are tuples that allow their elements to be accessed by name instead of just index!
I think this is a subtle implementation of a Monad-like thing, specifically something in the same spirit of the continuation monad.
Monads are a functional programming construction used to simulate state between different steps of a computation (Remember that a functional language is stateless).
What a monad does is to chain different functions, creating a "computation pipeline" where each step knows about the current state of the computation.
Monads have two primary pilars:
The Wikipedia has very good examples and explanations about monads.
Let me rewrite the given C++14 code:
auto list = []( auto... xs ) { return [=]( auto access ) { return access(xs...); }; };
I think here we identify the return
function of a monad: Takes the value and returns it in a Monadic way. Specifically, this return returns a functor (In the mathematical sense, not a C++ functor) which goes from the "tuple" category to the variadic pack category.
auto pack_size = [](auto... xs ) { return sizeof...(xs); };
pack_size
is just a normal function. It would be used in a pipeline to do some work.
auto bind = []( auto xs , auto op ) { return xs(op); };
And length
is only a non-generic version of something near to the monad bind
operator, an operator which takes a monadic value from a previous pipeline step, and bypasses it to the specified function (Function which really does the work). That function is the functionality done by this computation step.
Finally your call could be rewritten as:
auto result = bind(list(1,'2',"3"), pack_size);
So, whats the name of this tuple creation idiom? Well, I think this could be called "monad-like tuples", since its not exactly a monad, but the tuple representation and expansion works in a similar way, remaining to the Haskell continuation monad.
Just for the shake of funny C++ programming, I have followed exploring this monad-like thing. You could find some examples here.
I would call this idiom tuple-continuator or more generally, monadic-continuator. It is most definitely an instance of a continuation monad. A great introduction for continuation monad for C++ programmers is here. In essence, the list
lambda above takes a value (a variadic parameter-pack) and returns a simple 'continuator' (the inner closure). This continuator, when given a callable (called access
), passes the parameter pack into it and returns whatever that callable returns.
Borrowing from the FPComplete blogpost, a continuator is more or less like the following.
template<class R, class A> struct Continuator { virtual ~Continuator() {} virtual R andThen(function<R(A)> access) = 0; };
The Continuator
above is abstract--does not provide an implementation. So, here is a simple one.
template<class R, class A> struct SimpleContinuator : Continuator<R, A> { SimpleContinuator (A x) : _x(x) {} R andThen(function<R(A)> access) { return access(_x); } A _x; };
The SimpleContinuator
accepts one value of type A
and passes it on to access
when andThen
is called. The list
lambda above is essentially the same. It is more general. Instead of a single value, the inner closure captures a parameter-pack and passes it to the access
function. Neat!
Hopefully that explains what it means to be a continuator. but what does it mean to be a monad? Here is a good introduction using pictures.
I think the list
lambda is also a list monad, which is implemented as a continuation monad. Note that continuation monad is the mother of all monads. I.e., you can implement any monad with a continuation monad. Of course, list monad is not out of reach.
As a parameter-pack is quite naturally a 'list' (often of heterogeneous types), it makes sense for it to work like a list/sequence monad. The list
lambda above is a very interesting way of converting C++ parameter-packs to a monadic structure. Therefore, operations can be chained one after another.
The length
lambda above, however, is a bit disappointing because it breaks the monad and the nested lambda inside simply returns an integer. There is arguably a better way to write the length 'getter' as shown below.
----Functor----
Before we can say the list lambda is a monad, we have to show that it is a functor. I.e., fmap must be written for list.
The list lambda above serves as the creator of the functor from a parameter pack---essentially it serves as the return
. That created functor keeps the parameter-pack with itself (capture) and it allows 'access' to it provided you give a callable that accepts a variable number of arguments. Note that the callable is called EXACTLY-ONCE.
Lets write fmap for such a functor.
auto fmap = [](auto func) { return [=](auto ...z) { return list(func(z)...); }; };
The type of the func must be (a -> b). I.e., in C++ speak,
template <class a, class b> b func(a);
The type of fmap is fmap: (a -> b) -> list[a] -> list[b]
I.e., in C++ speak,
template <class a, class b, class Func> list<b> fmap(Func, list<a>);
I.e., fmap simply maps list-of-a to a list-of-b.
Now you can do
auto twice = [](auto i) { return 2*i; }; auto print = [](auto i) { std::cout << i << " "; return i;}; list(1, 2, 3, 4) (fmap(twice)) (fmap(print)); // prints 2 4 6 8 on clang (g++ in reverse)
Therefore, it is a functor.
----Monad----
Now, lets try to write a flatmap
(a.k.a. bind
, selectmany
)
Type of flatmap is flatmap: (a -> list[b]) -> list[a] -> list[b].
I.e., given a function that maps a to a list-of-b and a list-of-a, flatmap return a list-of-b. Essentially, it takes each element from list-of-a, calls func on it, receives (potentially empty) list-of-b one-by-one, then concatenates all the list-of-b, and finally returns the final list-of-b.
Here's an implementation of flatmap for list.
auto concat = [](auto l1, auto l2) { auto access1 = [=](auto... p) { auto access2 = [=](auto... q) { return list(p..., q...); }; return l2(access2); }; return l1(access1); }; template <class Func> auto flatten(Func) { return list(); } template <class Func, class A> auto flatten(Func f, A a) { return f(a); } template <class Func, class A, class... B> auto flatten(Func f, A a, B... b) { return concat(f(a), flatten(f, b...)); } auto flatmap = [](auto func) { return [func](auto... a) { return flatten(func, a...); }; };
Now you can do a lot of powerful things with a list. For example,
auto pair = [](auto i) { return list(-i, i); }; auto count = [](auto... a) { return list(sizeof...(a)); }; list(10, 20, 30) (flatmap(pair)) (count) (fmap(print)); // prints 6.
The count function is a monad-perserving operation because it returns a list of single element. If you really want to get the length (not wrapped in a list) you have to terminate the monadic chain and get the value as follows.
auto len = [](auto ...z) { return sizeof...(z); }; std::cout << list(10, 20, 30) (flatmap(pair)) (len);
If done right, the collection pipeline pattern (e.g., filter
, reduce
) can now be applied to C++ parameter-packs. Sweet!
----Monad Laws----
Let's make sure the list
monad satisfies all three monad laws.
auto to_vector = [](auto... a) { return std::vector<int> { a... }; }; auto M = list(11); std::cout << "Monad law (left identity)\n"; assert(M(flatmap(pair))(to_vector) == pair(11)(to_vector)); std::cout << "Monad law (right identity)\n"; assert(M(flatmap(list))(to_vector) == M(to_vector)); std::cout << "Monad law (associativity)\n"; assert(M(flatmap(pair))(flatmap(pair))(to_vector) == M(flatmap([=](auto x) { return pair(x)(flatmap(pair)); }))(to_vector));
All asserts are satisfied.
----Collection Pipeline----
Although the above 'list' lambda is provably a monad and shares characteristics of the proverbial 'list-monad', it is quite unpleasant. Especially, because the behavior of common collection pipeline combinators, such as filter
(a.k.a where
) does not meet common expectations.
The reason is just how C++ lambdas work. Each lambda expression produces a function object of a unique type. Therefore, list(1,2,3)
produces a type that has nothing to do with list(1)
and an empty list, which in this case would be list()
.
The straight-forward implementation of where
fails compilation because in C++ a function can not return two different types.
auto where_broken = [](auto func) { return flatmap([func](auto i) { return func(i)? list(i) : list(); // broken :-( }); };
In the above implementation, func returns a boolean. It's a predicate that says true or false for each element. The ?: operator does not compile.
So, a different trick can be used to allow continuation of the collection pipeline. Instead of actually filtering the elements, they are simply flagged as such---and that's what makes it unpleasant.
auto where_unpleasant = [](auto func) { return [=](auto... i) { return list(std::make_pair(func(i), i)...); }; };
The where_unpleasant
gets the job done but unpleasantly...
For example, this is how you can filter negative elements.
auto positive = [](auto i) { return i >= 0; }; auto pair_print = [](auto pair) { if(pair.first) std::cout << pair.second << " "; return pair; }; list(10, 20) (flatmap(pair)) (where_unpleasant(positive)) (fmap(pair_print)); // prints 10 and 20 in some order
----Heterogeneous Tuples----
So far the discussion was about homogeneous tuples. Now lets generalize it to true tuples. However, fmap
, flatmap
, where
take only one callback lambda. To provide multiple lambdas each working on one type, we can overload them. For example,
template <class A, class... B> struct overload : overload<A>, overload<B...> { overload(A a, B... b) : overload<A>(a), overload<B...>(b...) {} using overload<A>::operator (); using overload<B...>::operator (); }; template <class A> struct overload<A> : A{ overload(A a) : A(a) {} using A::operator(); }; template <class... F> auto make_overload(F... f) { return overload<F...>(f...); } auto test = make_overload([](int i) { std::cout << "int = " << i << std::endl; }, [](double d) { std::cout << "double = " << d << std::endl; }); test(10); // int test(9.99); // double
Let's use the overloaded lambda technique to process a heterogeneous tuple continuator.
auto int_or_string = make_overload([](int i) { return 5*i; }, [](std::string s) { return s+s; }); list(10, "20") (fmap(int_or_string)) (fmap(print)); // prints 2020 and 50 in some order
Finally, Live Example
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With