Is there a name for this tuple-creation idiom?

Question

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.

Answer 1

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:

• A return function, which takes a value and returns it in a Monad-ready form.
• A bind function, which takes a Monad-ready value (From the previous pipeline step) and unwraps it to its original from to pass the value to the next step.

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.

Edit: More fun

Just for the shake of funny C++ programming, I have followed exploring this monad-like thing. You could find some examples here.

Answer 2

This looks like a form of continuation passing style.

The rough idea of CPS is this: instead of having a function (say f) return some value, you give to f another argument, which is a function, called a continuation. Then, f calls this continuation with the return value instead of returning. Let's take an example:

int f (int x) { return x + 42; }

becomes

void f (int x, auto cont) { cont (x + 42); }

The call is a tail call, and can be optimized into a jump (this is why TCO is mandated in some languages, like Scheme, whose semantics rely on some form of transformation into CPS).

Another example:

void get_int (auto cont) { cont (10); }
void print_int (int x) { printf ("%d", x), }

You can now do get_int (std::bind (f, _1, print_int)) to print 54. Note that all the continuation calls are always tail calls (the call to printf is also a continuation call).

A well-known example is asynchronous callbacks (AJAX calls in javascript for instance): you pass a continuation to a routine executing in parallel.

Continuations can be composed (and form a monad, in case you're interested), as in the above example. In fact it is possible to transform a (functional) program entirely into CPS, so that every call is a tail call (and then you need no stack to run the program !).

Answer 3

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