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
