Changing a runtime algorithm to compile time for mpl::fold

[JUAN DENT]

Hi,

I am having trouble implementing and even conceptualizing an implementation of the Boost mpl::fold algorithm. I created a runtime version easily but not a compile time. I would greatly appreciate help on this endeavor.

The code for runtime version is as follows:

auto tail(sequence seq) -> sequence
{
	// skip the first element
	auto start = seq.begin();
	++start;
	sequence res{ start, seq.end() };
	return res;
}

auto head(const sequence& seq) -> int
{
	return seq[0];
}

template<typename BinaryOp>
auto fold(sequence seq, sequence prev, BinaryOp op) -> sequence
{
	if (seq.empty())
	{
		return prev;
	}
	else		// combine the first element with prev
	{		// and process the rest recursively

		return fold(tail(seq), op(prev, head(seq)), op);
	}
}

I assume the declaration for fold would be something like this:

template<template <typename...> class Seq, typename Prev, typename BinaryOp>
struct fold
{};

and we would need compile time "functions"(probably in the form of structs) to implement head and tail...

I am really at a loss here. Will appreciate any help, especially if it does not use boost types (I want to see an implementation from zero).

Really appreciative of any help!!

Juan Dent

[mbozzi]

Something like this?

#include <type_traits>

struct nil_t;
template <typename... Ts> struct vector;

template <typename...> struct head { using type = nil_t; };
template <template <typename...> class Seq, typename First, typename... Rest>
struct head<Seq<First, Rest...>> {
  using type = First;
};

template <typename Seq> using head_t = typename head<Seq>::type;

template <typename...> struct tail { using type = nil_t; };
template <template <typename...> class Seq, typename First, typename... Rest>
struct tail<Seq<First, Rest...>> {
  using type = Seq<Rest...>;
};

template <typename Seq> using tail_t = typename tail<Seq>::type;

template <typename Seq, typename State, typename Fn> struct fold {
  using type =
      typename fold<tail_t<Seq>,
                    typename Fn::template apply<head_t<Seq>, State>::type,
                    Fn>::type;
};
template <typename State, typename Fn> struct fold<nil_t, State, Fn> {
  using type = State;
};

template <typename Seq, typename State, typename Fn>
using fold_t = typename fold<Seq, State, Fn>::type;

template <int I> using int_ = std::integral_constant<int, I>;
template <typename N> using succ = int_<N::value + 1>;

struct accumulate_if_float {
  template <typename T, typename Sum> struct apply {
    using type =
        std::conditional_t<std::is_floating_point<T>::value, succ<Sum>, Sum>;
  };
};

template <typename Seq>
constexpr auto number_of_floats_v =
    fold_t<Seq, int_<0>, accumulate_if_float>::value;
using MySeq = vector<long, float, short, double, float, long, long double>;

static_assert(number_of_floats_v<MySeq> == 4);

Live demo:
http://coliru.stacked-crooked.com/a/d810e57db127c838

Based off of the documentation here:
http://www.boost.org/doc/libs/1_66_0/libs/mpl/doc/refmanual/fold.html

[JUAN DENT]

Wonderful mbozzi, thanks!!

MSVC insists in requiring a typename in the apply structure inside accumulate_if_float like so:

struct accumulate_if_float
{
	template<typename T, typename Sum>
	struct apply
	{
		using type = typename std::conditional<std::is_floating_point<T>::value, succ<Sum>, Sum>::type;
	};
};

Also, it seems unnecessary to declare both head and tail as variadic templates - it does not hurt actually, but a simple typename will do easily well - as far as I can tell.

But many thanks for this solution!! Great work!!

Juan

[mbozzi]

MSVC insists in requiring a typename in the apply structure inside accumulate_if_float like so:

Yes, if you use std::conditional instead of std::conditional_t.

[JUAN DENT]

Oh boy!! Did not see the _t in conditional_t!
I am sorry.
Still, your code just supplied what I needed!
Thank you so much!

Juan