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
list
is a monad, isn't? A function expecting other function to complete the computation haskell.org/haskellwiki/MonadList:X->(X->Y)->Y
. Which should be easier to find.