Archive for April, 2015

Recursive lambdas

Thursday, April 16th, 2015

One can assign a lambda to auto or to std::function. Normally one would assign a lambda to auto to avoid possible unwanted allocation from std::function. But if you want recursion, you need to be able to refer to the lambda variable inside the lambda, and you can’t do that if it’s assigned to auto. So how do you do recursive lambdas without using std::function?

Use a fixed-point combinator (y-combinator) of course.

#include <functional>
#include <iostream>
 
template<typename F>
struct Fix
{
  Fix(const F& f)
    : m_f(f)
  {}
 
  Fix(F&& f)
    : m_f(std::move(f))
  {}
 
  template <typename T>
  auto operator()(T t) const
  {
    return m_f(*this, t);
  }
 
  F m_f;
};
 
template<typename F>
auto fix(F&& f)
{
  return Fix<F>(std::forward<F>(f));
}
 
int main(void)
{
  auto f = fix(
      [] (auto& f, int x) -> int
      {
        if (x <= 2) return 1;
        return f(x-1) + f(x-2);
      });
  std::cout << f(6) << std::endl;
 
  return 0;
}

This code compiles with GCC 4.9.1, Clang 3.4.2 or MSVC 2015 preview (and produces “8” as the output). Clang allows omission of the lambda’s trailing return type.

Rules for using <random>

Wednesday, April 8th, 2015

These days, it’s easy to do the right thing.

Don’t do this:

  • Don’t use std::rand(). Ever.
  • Don’t use std::random_shuffle() to permute containers. (Too easy to misuse; can use std::rand() under the hood.)
  • Don’t use any kind of clock for a seed.
  • Don’t use mod (%) to get a random value into a range. It introduces bias.
  • Don’t use std::default_random_engine – it’s probably not the best choice and can vary by implementation.

Do this:

  • Use std::random_device() as a source of entropy. It should be the best randomness your OS can supply.
  • Use std::shuffle() to permute containers. Its interface doesn’t permit misuse like std::random_shuffle().
  • Use std::mt19937 (or std::mt19937_64) as an RNG engine. (Or consider PCG, but that’s not standard – yet.)
  • Seed the engine with as much seed data as it requires for its internal state (using its state_size member), otherwise you’re throwing away entropy. For std::mt19937 this is 624 32-bit values (not just a single 32-bit value). Use std::seed_seq to help with initialization.
  • RNG engines (particularly std::mt19937) can be expensive to initialize (and have large amounts of internal state), so don’t put them on the stack unnecessarily. Consider using thread_local.
  • Use std::uniform_int_distribution (and the other distributions) to get your random number into the required range. The distributions are carefully crafted to be unbiased (why you shouldn’t use %). Note that they work on closed (inclusive) ranges, not half-open ranges – otherwise the max value would be unreachable.

Wrong:

// init RNG
srand(time(NULL));
 
// get random number
int n = rand() % 100;

Right:

// init RNG
std::array<int, std::mt19937::state_size> seed_data;
std::random_device r;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
std::mt19937 gen(seq);
 
// get random number
std::uniform_int_distribution<int> dis(0,99);
int n = dis(gen);

Edit: Alternatively, Melissa O’Neill has produced randutils which wraps C++11 random number generation in a nice interface, and does the right thing. She knows what she’s talking about: her work on randomness is worth your time.

C++ Tuples: the missing functionality

Monday, April 6th, 2015

C++ provides a strange mix of compile-time and runtime functionality for dealing with tuples. There are some interesting parts, like std::tie to destructure a tuple, and std::tuple_cat to join together several tuples into one. So there is evidence that the standard has been influenced by some functional programming ideas, but I don’t think the full power of tuples has been realized (in both senses), and I found myself thinking about some missing parts.

Like why do we have std::tuple_cat and std::get<0> (aka std::tuple_head), but not std::tuple_cons or std::tuple_tail? So here are some possible implementations.

First, something missing from type_traits which will help us constrain things:

template <typename T>
struct is_tuple : public std::false_type {};
 
template <typename... Ts>
struct is_tuple<std::tuple<Ts...>> : public std::true_type {};

Both tuple_cons and tuple_tail can make use of an expansion of std::index_sequence to work their magic, with a user-facing function that provides the appropriate std::index_sequence to an overload.

For tuple_cons, we just call std::make_tuple with the new element and the result of expanding std::get across the other tuple:

template <typename U, typename T, std::size_t ...Is>
auto tuple_cons(U&& u, T&& t, std::index_sequence<Is...>,
    std::enable_if_t<is_tuple<std::decay_t<T>>::value>* = nullptr)
{
  return std::make_tuple(std::forward<U>(u), 
                         std::get<Is>(std::forward<T>(t))...);
}
 
template <typename U, typename T>
auto tuple_cons(U&& u, T&& t,
    std::enable_if_t<is_tuple<std::decay_t<T>>::value>* = nullptr)
{
  using Tuple = std::decay_t<T>;
  return tuple_cons(std::forward<U>(u), std::forward<T>(t),
      std::make_index_sequence<std::tuple_size<Tuple>::value>());
}

And for tuple_tail, we construct a std::index_sequence of length n-1, then offset it by one in the expansion to obtain the tail:

template <typename T, std::size_t ...Is>
auto tuple_tail(T&& t, std::index_sequence<Is...>,
    std::enable_if_t<is_tuple<std::decay_t<T>>::value>* = nullptr)
{
  return std::make_tuple(std::get<Is + 1>(std::forward<T>(t))...);
}
 
template <typename T>
auto tuple_tail(T&& t, 
    std::enable_if_t<is_tuple<std::decay_t<T>>::value>* = nullptr)
{
  using Tuple = std::decay_t<T>;
  return tuple_tail(std::forward<T>(t),
      std::make_index_sequence<std::tuple_size<Tuple>::value - 1>());
}