N3404=12-0094
2012-09-22
Mike Spertus, Symantec
mike_spertus@symantec.com

Tuple Tidbits

Overview

The purpose of this paper is to propose two extensions to tuple:

  1. Following the suggestion in [1], make tuples addressable by type as well as by index.
  2. Make tuple functorial in category-theoretical sense

Both of these are implemented

Addressing tuples by type

This is an idea is inspired by Alexandrescu's Modern C++ Design [1] tuple discussion. Suppose we have a function get_employee_info that returns some employee information in a tuple<employee_id, salary, office>. Saying something like get<2>(get_employee_info(...) doesn't really make it that obvious that we are looking for the employee's office. Furthermore, if we later become interested in returning another employee attribute, we may need to adjust indexes all over the program.

This paper proposes allowing fields to be accessed by type, so the much clearer get<office>(get_employee_info(...)) could be used interchangeably with get<2>(get_employee_info(...). The only technical issue is what to do if a tuple contains repeated types. In that case, we require a compile error. tuple<string, string, int> t("foo", "bar", 7); string s = get<string>(t); // ERROR. Ambiguous access

Implementation status

Yes. The approach in Loki suffices, because you can cast down to whichever Holder<T> you want. Also, I have my Advanced C++ students implement type-addressable tuples each year.

Functoriality

The basic idea is simple. We want code like the following to work. auto funcs = make_tuple(sqrt, strlen, atof); auto vals = make_tuple(9, "foo", "7.3"); auto result = funcs(vals); // result is tuple<double, size_t, double>(3, 3, 7.3)

Of course, there is no need to limit oneself to ordinary functions. For example, auto funcs = make_tuple(bind(std::multiplies<int, int>, _1, _1), function(&string::size), [](char const *cp)->double { istringstream is(cp); double d; is >> d; return d; }); auto vals = make_tuple(9, "foo", "7.3"); auto result = funcs(vals); // result is tuple<int, size_t, double>(81, 3, 7.3)

For a less artificial example, consider a function get_order that returns a tuple<date, map<item, int>> representing an order placed by a company. Suppose we want to convert this to a point on a graph, where the x coordinate is the day number of the date and the y coordinate is the total number of items in the order: int days_from_epoch(date d); int items_in_order(map<item, int> const &order_items) { // Just add up all the order counts return accumulate(order_items.begin(), order_items.end(), 0, [](int acc, pair<item, int> const &p) { return acc + p.second; }); } auto point = make_tuple(days_from_epoch, items_in_order)(get_order(/* ... */));

Of course, the above example could have been done with a pair as easily as with a tuple, so we also propose an analogous change for pair.

Variations

As an alternative to the definition of tuple::operator(), we could create a free function apply in its place: auto result = apply(funcs, vals); // funcs, vals as above

Warning:
This is a different meaning than proposed for apply in N1483 [3]. This is also an important use case that we detailed in the EWG paper n3416. Briefly, that paper supports code like: bool f(int, double, string); auto t = make_tuple(4, 3.14); bool result = f(t..., "foo");This provides a superset of the functionality of the functionality of apply in N1483

Philosophy

While the above examples are meant to stand on their own merit, we can view this as desirable from a more theoretical approcah. More formally, we can think of the type tuple as a cartesian product of its component types. One of the fundamental insights of category theory (e.g., [4]) is that cartesian products derive their power because they act not only on sets, but are in fact functors (in the category-theoretic sense), allowing ones to take cartesian products of arrows (i.e., functions) [2, §6.2.17]. In those terms, this proposal elevates tuple from simply being a way to create new types to being a full (category-theoretic) functor.

Implementation Status

Yes. Please contact the author for a copy of the implementation

 

Wording

Change §20.4.1 [tuple.general] paragraph 2

// 20.4.2.6, element access:
template <size_t I, class... Types>
  typename tuple_element<I, tuple<Types...> >::type& get(tuple<Types...>&) noexcept;
template <size_t I, class... types>
  typename tuple_element<I, tuple<Types...> >::type&& get(tuple<Types...>&&) noexcept;
template <size_t I, class... types>
  typename tuple_element<I, tuple<Types...> >::type const& get(const tuple<Types...>&) noexcept;
template <typename T, class... Types>
  typename T& get(tuple<Types...>&) noexcept;
template <typename T, class... types>
  typename T&& get(tuple<Types...>&&) noexcept;
template <typename T, class... types>
  typename T const& get(const tuple<Types...>&) noexcept;

Change §20.4.2:

    // 20.4.2.3, tuple swap
    void swap(tuple&) noexcept(see below);
    // 20.4.2.x, tuple functoriality
    template<class.. UTypes>
     tuple<typename result_of<Types(UTypes)>::type...>operator()(tuple<UTypes...> &u);
   template<class.. UTypes>
     tuple<typename result_of<Types(UTypes)>::type...>operator()(const tuple<UTypes...> &u);
   template<class.. UTypes>
     tuple<typename result_of<Types(UTypes)>::type...>operator()(tuple<UTypes...> &u) const;
   template<class.. UTypes>
     tuple<typename result_of<Types(UTypes)>::type...>operator()(const tuple<UTypes...> &u) const;
  };
}

Add a new section §20.4.2.x [tuple.functorial]:

template<class.. UTypes>
    tuple<typename result_of<Types(UTypes)>::type...>operator()(tuple<UTypes...> &u);
template<class.. UTypes>
    tuple<typename result_of<Types(UTypes)>::type...>operator()(const tuple<UTypes...> &u);
template<class.. UTypes>
    tuple<typename result_of<Types(UTypes)>::type...>operator()(tuple<UTypes...> &u) const;
template<class.. UTypes>
    tuple<typename result_of<Types(UTypes)>::type...>operator()(const tuple<UTypes...> &u) const;
Requires: sizeof...(Types) == sizeof...(UTypes) and for all 0 <= i < sizeof...(Types), the expression get<i>(*this)(get<i>(u)) is valid.
Returns: The result that would be achieved by make_tuple(get<0>(*this)(get<0>(u)), get<1>(*this)(get<0>(1)),/* ... */).

Add the following to the end of §20.4.2.6 [tuple.elem]:

template <typename T, class... Types>
  T& get(tuple<Types...>& t) noexcept;
Requires: The type T occurs exactly once in Types.... Otherwise, the program is ill-formed.
Returns: A reference to the element of t corresponding to the type T in Types...
template <typename T, class... Types>
  T&& get(tuple<Types...>&& t) noexcept;
Effects: Equivalent to return std::forward<T&&>(get<i>(t));
Note: if a T in Types is some reference type X&, the return type is X&, not X&&. However, if the element type is a non-reference type T, the return type is T&&.
template <typename T, class... Types>
  T& get(const tuple<Types...>& t) noexcept;
Requires: The type T occurs exactly once in Types.... Otherwise, the program is ill-formed.
Returns: A const reference to the element of t corresponding to the type T in Types...

[ Note: Constness is shallow. If a T in Types is some reference type X&, the return type is X&, not const X&. However, if the element type is non-reference type T, the return type is const T&. This is consistent with how constness is defined to work for member variables of reference type. —end note ]
 

References

[1] Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied. Addison Wesley, 2001.

[2] Bar, Category Theory. Lecture Notes for ESSLLI, http://www.ling.ohio-state.edu/~plummer/courses/winter09/ling681/barrwells.pdf.

[3] Gregor, Powell, Järvi, Typesafe variable-length function and template argument lists. Technical Report N1483=03-0066, ISO/IEC JTC 1, Information technology, Subcommittee SC 22, Programming language C++, 2003. www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1483.pdf.

[4] MacLane, Categories for the Working Mathematician, 2nd edition.Springer-Verlag, 1997.