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

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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:

1
2
3
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
Something like this?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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
Last edited on
Wonderful mbozzi, thanks!!

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

1
2
3
4
5
6
7
8
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
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.
Last edited on
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
Registered users can post here. Sign in or register to post.