1 /*
2 * transducer.cpp
3 *
4 * Created on: May 9, 2019
5 * Author: bacoo zhao
6 * Compile: g++ -g -Wall -std=c++14 transducer.cpp -o transducer
7 * Reference: http://vitiy.info/cpp14-how-to-implement-transducers/
8 * http://vitiy.info/templates-as-first-class-citizens-in-cpp11/
9 * http://vitiy.info/functional-pipeline-in-c11/
10 */ 11 12 #include <functional>
13 #include <type_traits>
14 #include <utility>
15 #include <vector>
16 #include <
string>
17 #include <iostream>
18 19 template<typename T>
20 void print_type_trait() {
21 std::cout << __PRETTY_FUNCTION__ << std::endl;
22 }
23 #define PRINT_TYPE_TRAIT(x) print_type_trait<decltype(x)>()
24 25 namespace fn_detail {
26 27 template<typename G, typename
Ts>
28 struct tr_transducer {
29 std::tuple<Ts
>
params;
30 31 tr_transducer(Ts
ts) :
32 params(std::make_tuple(ts
)) {
33 }
34 35 template<typename RF>
36 auto
operator()(RF&& step)
const {
37 return this->make(std::forward<RF>(step),
38 std::make_index_sequence<
sizeof(Ts)>());
39 }
40 41 template<typename RF, std::size_t
indexes_t>
42 auto make(RF step, std::index_sequence<indexes_t
>)
const 43 -> typename G::template apply<RF, Ts
>
44 {
45 return {std::forward<RF>(step), std::
get<indexes_t>(
params)
};
46 }
47 };
48 49 template<typename
T>
50 void noop(T
ts) {
51 }
52 53 struct tr_map_gen {
54 template<typename ReducingFnT, typename MappingT>
55 struct apply {
56 ReducingFnT step;
57 MappingT mapping;
58 59 template<typename StateT, typename
InputTs>
60 bool operator()(StateT&
out, InputTs&&
ins) {
61 return step(
out, mapping(std::forward<decltype(ins)>(ins)
));
62 }
63 };
64 };
65 66 struct tr_filter_gen {
67 template<typename ReducingFnT, typename FilterT>
68 struct apply {
69 ReducingFnT step;
70 FilterT pred;
71 72 template<typename StateT, typename
InputTs>
73 bool operator()(StateT&
out, InputTs&&
ins) {
74 if (pred(std::forward<decltype(ins)>(ins)
))
75 return step(
out, std::forward<decltype(ins)>(ins)
);
76 else 77 return true;
78 }
79 };
80 };
81 82 struct tr_enumerate_gen {
83 template<typename ReducingFnT, typename N>
84 struct apply {
85 ReducingFnT step;
86 int n;
87 88 template<typename StateT, typename
InputTs>
89 bool operator()(StateT&
out, InputTs&&
ins) {
90 return step(
out, n++, std::forward<decltype(ins)>(ins)
);
91 }
92 };
93 };
94 95 struct tr_limit_gen {
96 template<typename ReducingFnT, typename N1, typename N2>
97 struct apply {
98 ReducingFnT step;
99 int n;
100 int limit;
101 102 template<typename StateT, typename
InputTs>
103 bool operator()(StateT&
out, InputTs&&
ins) {
104 return (n++ > limit) ?
105 false : step(
out, std::forward<decltype(ins)>(ins)
);
106 }
107 };
108 };
109 110 struct tr_each_gen {
111 template<typename ReducingFnT, typename EachFnT>
112 struct apply {
113 ReducingFnT step;
114 EachFnT each;
115 116 template<typename StateT, typename
InputTs>
117 bool operator()(StateT&
out, InputTs&&
ins) {
118 each(std::forward<decltype(ins)>(ins)
);
119 return true;
120 }
121 };
122 };
123 124 }
// end of namespace fn_detail
125 126 template<typename T>
127 auto tr_map(T f) {
128 return fn_detail::tr_transducer<fn_detail::tr_map_gen, T>(f);
129 }
130 131 template<typename T>
132 auto tr_filter(T pred) {
133 return fn_detail::tr_transducer<fn_detail::tr_filter_gen, T>(pred);
134 }
135 136 auto tr_enumerate(
int n = 0) {
137 return fn_detail::tr_transducer<fn_detail::tr_enumerate_gen,
int>(n);
138 }
139 140 auto tr_limit(
int limit) {
141 return fn_detail::tr_transducer<fn_detail::tr_limit_gen,
int,
int>(1, limit);
142 }
143 144 template<typename T>
145 auto tr_each(T each) {
146 return fn_detail::tr_transducer<fn_detail::tr_each_gen, T>(each);
147 }
148 149 /// The inversed chain of functors is actually just a tuple of functors
150 template<typename
FNs>
151 class fn_chain_reversed {
152 private:
153 const std::tuple<FNs
> functions;
154 155 template<std::size_t I, typename Arg>
156 inline typename std::enable_if<I ==
sizeof(FNs) - 1, decltype(std::
get<I>(functions)(std::declval<Arg>())) >::type
157 call(Arg arg)
const158 {
159 return std::
get<I>(functions)(std::forward<Arg>(arg));
160 }
161 162 template <std::size_t N, std::size_t I, typename Arg>
163 struct final_type : final_type<N-1, I+1, decltype(std::
get<I>(functions)(std::declval<Arg>())) > {};
164 165 template <std::size_t I, typename Arg>
166 struct final_type<0, I, Arg> {
167 using type = decltype(std::
get<I>(functions)(std::declval<Arg>()));
168 };
169 170 template <std::size_t I, typename Arg>
171 inline typename std::enable_if<I <
sizeof(FNs) - 1, typename final_type<
sizeof(FNs) - 1 - I, I, Arg>::type >::type
172 call(Arg arg)
const173 {
174 return this->call<I+1>(std::
get<I>(functions)(std::forward<Arg>(arg)));
175 }
176 177 static const bool isFunctionalChain =
true;
178 179 public:
180 fn_chain_reversed() : functions(std::tuple<>()) {}
181 fn_chain_reversed(std::tuple<FNs
> functions) : functions(functions) {}
182 183 // add function into chain (inversed order)
184 template< typename F >
185 inline auto add(
const F& f)
const -> fn_chain_reversed<F,FNs
>
186 {
187 return fn_chain_reversed<F,FNs
>(std::tuple_cat(std::make_tuple(f), functions));
188 }
189 190 // call whole functional chain
191 template <typename Arg>
192 inline auto
operator()(Arg arg)
const -> decltype(
this->call<0,Arg>(arg))
193 {
194 return call<0>(std::forward<Arg>(arg));
195 }
196 197 };
198 199 template<typename
FNs, typename F>
200 inline auto
operator|(fn_chain_reversed<FNs
> && transducer,
201 F&& rf) -> decltype(transducer.add(rf)) {
202 return transducer.add(std::forward<F>(rf));
203 }
204 205 template<typename T, typename
FNs>
206 struct fn_isNotFunctionalChain {
207 static const bool value =
true;
208 };
209 210 template<>
211 struct fn_isNotFunctionalChain<fn_chain_reversed<> > {
212 static const bool value =
false;
213 };
214 215 template<typename T,
class F, typename = std::enable_if_t<
216 fn_isNotFunctionalChain<F>::value> >
217 auto
operator|(
const F& f, T&& param) -> decltype(f(param)) {
218 return f(std::forward<T>(param));
219 }
220 221 #define tr fn_chain_reversed<>()
222 223 template<std::size_t Index, std::size_t Max>
224 struct tuple_all_neq_t {
225 template<typename Tuple1T, typename Tuple2T>
226 bool operator()(Tuple1T&& t1, Tuple2T&& t2) {
227 return std::
get<Index>(std::forward<Tuple1T>(t1))
228 != std::
get<Index>(std::forward<Tuple2T>(t2))
229 && tuple_all_neq_t<Index + 1, Max> { }(
230 std::forward<Tuple1T>(t1), std::forward<Tuple2T>(t2));
231 }
232 };
233 234 template<std::size_t Max>
235 struct tuple_all_neq_t<Max, Max> {
236 template<typename Tuple1T, typename Tuple2T>
237 bool operator()(Tuple1T&&, Tuple2T&&) {
238 return true;
239 }
240 };
241 242 template<typename Tuple1T, typename Tuple2T>
243 bool tuple_all_neq(Tuple1T&& t1, Tuple2T&& t2) {
244 constexpr auto size1 = std::tuple_size<std::decay_t<Tuple1T> >::value;
245 constexpr auto size2 = std::tuple_size<std::decay_t<Tuple2T> >::value;
246 247 using impl_t = tuple_all_neq_t<0u, (size1 > size2 ? size2 : size1)>;
248 249 return impl_t { }(std::forward<Tuple1T>(t1), std::forward<Tuple2T>(t2));
250 }
251 252 template<typename RF, typename A, std::size_t
Indices, typename
Ranges>
253 auto fn_accum_impl(std::index_sequence<Indices
>, RF&& step, A&
out,
254 Ranges
ranges) {
255 auto firsts = std::make_tuple(std::begin(ranges)
);
256 auto lasts = std::make_tuple(std::end(ranges)
);
257 258 bool ok =
true;
259 // just loop once
260 while (tuple_all_neq(firsts, lasts) && (ok)) {
261 ok = step(
out, std::forward< decltype(*std::begin(ranges)) >(*std::
get<Indices>(firsts))
);
262 fn_detail::noop(++std::
get<Indices>(firsts)
);
263 }
264 }
265 266 template<typename T, typename RF, typename C, typename
Ins>
267 auto fn_tr_transduce(C init, T&& transducer, RF&& reducingFunction, Ins
ins) {
268 C
out = init;
269 fn_accum_impl(std::make_index_sequence<
sizeof(Ins)> {},
270 transducer(reducingFunction),
271 out,
272 (std::forward<Ins>(ins))
);
273 return std::move(
out);
274 }
275 276 template<typename RF, typename C, typename
Ins>
277 auto fn_into_vector(RF step, C input, Ins
ins) {
278 return fn_tr_transduce(
279 std::vector<std::decay_t<decltype(*std::begin(input))>>(), step,
280 [] (auto&
out, auto input) {
281 out.push_back(input);
282 return true;
283 }, std::forward<C>(input), (std::forward<Ins>(ins))
);
284 }
285 286 template<typename T, typename C, typename
Ins>
287 auto fn_tr_reduce(C&& init, T&& step, Ins
ins) {
288 C&&
out = std::forward<C>(init);
289 fn_accum_impl(std::make_index_sequence<
sizeof(Ins)> {},
290 std::forward<T>(step),
291 out,
292 (std::forward<Ins>(ins))
);
293 return std::move(
out);
294 }
295 296 template<typename T, typename
Ins>
297 void fn_tr_end(T&& step, Ins
ins) {
298 auto step_wrap = step([](){});
299 int out = 0;
300 fn_accum_impl(std::make_index_sequence<
sizeof(Ins)> {},
301 std::forward<decltype(step_wrap)>(step_wrap),
302 out,
303 (std::forward<Ins>(ins))
);
304 }
305 306 void my_func(
int n,
int x) {
307 std::cout << n << ":" << x << std::endl;
308 }
309 int main(
int argc,
char* argv[]) {
310 std::vector<
int> input { 1, 2, 3, 4, 5, 6 };
311 312 {
313 auto piping = tr | tr_map([](
int x){
return 2*x;}) | tr_filter([](
int x){
return x > 3 && x < 10;}) | tr_limit(2);
314 auto transducer = piping([](std::vector<
int>&
out,
int x) {
315 out.push_back(x);
316 return true;
317 });
318 //[with T =
319 // fn_chain_reversed<
320 // fn_detail::tr_transducer<fn_detail::tr_limit_gen, int, int>,
321 // fn_detail::tr_transducer<fn_detail::tr_filter_gen, main(int, char**)::<lambda(int)> >,
322 // fn_detail::tr_transducer<fn_detail::tr_map_gen, main(int, char**)::<lambda(int)> >
323 // >
324 //]
325 PRINT_TYPE_TRAIT(piping);
326 //[with T =
327 // fn_detail::tr_map_gen::apply<
328 // fn_detail::tr_filter_gen::apply<
329 // fn_detail::tr_limit_gen::apply<
330 // main(int, char**)::<lambda(std::vector<int>&, int)>,
331 // int,
332 // int
333 // >,
334 // main(int, char**)::<lambda(int)>
335 // >,
336 // main(int, char**)::<lambda(int)>
337 // >
338 //]
339 PRINT_TYPE_TRAIT(transducer);
340 auto result = fn_tr_reduce(std::vector<
int>(), transducer, input);
341 // output:
342 // 4
343 // 6
344 for (auto x : result) {
345 std::cout << x << std::endl;
346 }
347 }
348 349 std::cout << "============" << std::endl;
350 351 {
352 auto result = fn_into_vector(tr |
353 tr_map([](
int x){
354 std::vector<
int> v;
355 for (
int i = 1; i <= x; ++i) {
356 v.push_back(i);
357 }
358 return v;
359 }) |
360 tr_map([](std::vector<
int> v) {
361 int sum = 0;
362 for (auto x : v) {
363 sum += x;
364 }
365 return sum;
366 }) |
367 tr_filter([](
int x){
368 return x > 4;
369 }), input);
370 // output:
371 // 6
372 // 10
373 // 15
374 // 21
375 for (auto x : result) {
376 std::cout << x << std::endl;
377 }
378 }
379 380 std::cout << "============" << std::endl;
381 382 {
383 std::vector<
int> input2 { 4, 5, 6, 7 };
384 auto result = fn_into_vector(tr | tr_map([](
int x,
int y){
return x + y; }) | tr_filter([](
int x){
return x > 5; }), input, input2);
385 // output:
386 // 7
387 // 9
388 // 11
389 for (auto x : result) {
390 std::cout << x << std::endl;
391 }
392 }
393 394 std::cout << "============" << std::endl;
395 396 {
397 auto enumerateStrings = (tr | tr_enumerate(1) | tr_limit(3) | tr_map([](
int idx, std::
string s) {
398 char buf[1024];
399 sprintf(buf, "elements[%d]=%s", idx, s.data());
400 return std::
string(buf);
401 }))([](std::vector<std::
string>&
out, std::
string s) {
402 out.push_back(s);
403 return true;
404 });
405 auto result = fn_tr_reduce(std::vector<std::
string>(), enumerateStrings, std::vector<std::
string>{"a","b","c", "d"});
406 // output:
407 // elements[1]=a
408 // elements[2]=b
409 // elements[3]=c
410 for (auto x : result) {
411 std::cout << x << std::endl;
412 }
413 }
414 415 std::cout << "============" << std::endl;
416 417 {
418 // output:
419 // elements[1]=4
420 // elements[3]=6
421 // elements[5]=8
422 fn_tr_end(tr | tr_enumerate() | tr_filter([](
int idx,
int n){
return idx % 2;}) |
423 tr_limit(3) | tr_each([](
int idx,
int n){ std::cout << "elements[" << idx << "]=" << n << std::endl; }),
424 std::vector<
int>{3, 4, 5, 6, 7, 8, 9});
425 }
426 427 return 0;
428 }
429