1 // Copyright 2015, Tobias Hermann and the FunctionalPlus contributors.
2 // https://github.com/Dobiasd/FunctionalPlus
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 #pragma once
8
9 #include <fplus/filter.hpp>
10 #include <fplus/composition.hpp>
11
12 #include <fplus/internal/asserts/functions.hpp>
13
14 namespace fplus
15 {
16
17 // API search type: generate : ((() -> a), Int) -> [a]
18 // Grab values from executing a nullary function
19 // to generate a sequence of amount values.
20 // generate(f, 3) == [f(), f(), f()]
21 // Can for example be used to generate a list of random numbers.
22 template <typename ContainerOut, typename F>
23 ContainerOut generate(F f, std::size_t amount)
24 {
25 internal::trigger_static_asserts<internal::nullary_function_tag, F>();
26 ContainerOut ys;
27 internal::prepare_container(ys, amount);
28 auto it = internal::get_back_inserter<ContainerOut>(ys);
29 for (std::size_t i = 0; i < amount; ++i)
30 {
31 *it = internal::invoke(f);
32 }
33 return ys;
34 }
35
36 // API search type: generate_by_idx : ((Int -> a), Int) -> [a]
37 // fwd bind count: 1
38 // Grab values from executing a unary function with an index
39 // to generate a sequence of amount values.
40 // generate_by_idx(f, 3) == [f(0), f(1), f(2)]
41 template <typename ContainerOut, typename F>
42 ContainerOut generate_by_idx(F f, std::size_t amount)
43 {
44 internal::
45 trigger_static_asserts<internal::unary_function_tag, F, std::size_t>();
46
47 ContainerOut ys;
48 internal::prepare_container(ys, amount);
49 auto it = internal::get_back_inserter<ContainerOut>(ys);
50 for (std::size_t i = 0; i < amount; ++i)
51 {
52 *it = internal::invoke(f, i);
53 }
54 return ys;
55 }
56
57 // API search type: repeat : (Int, [a]) -> [a]
58 // fwd bind count: 1
59 // Create a sequence containing xs concatenated n times.
60 // repeat(3, [1, 2]) == [1, 2, 1, 2, 1, 2]
61 template <typename Container>
repeat(std::size_t n,const Container & xs)62 Container repeat(std::size_t n, const Container& xs)
63 {
64 std::vector<Container> xss(n, xs);
65 return concat(xss);
66 }
67
68 // API search type: infixes : (Int, [a]) -> [[a]]
69 // fwd bind count: 1
70 // Return als possible infixed of xs with a given length.
71 // infixes(3, [1,2,3,4,5,6]) == [[1,2,3], [2,3,4], [3,4,5], [4,5,6]]
72 // length must be > 0
73 template <typename ContainerIn,
74 typename ContainerOut = std::vector<ContainerIn>>
infixes(std::size_t length,const ContainerIn & xs)75 ContainerOut infixes(std::size_t length, const ContainerIn& xs)
76 {
77 assert(length > 0);
78 static_assert(std::is_convertible<ContainerIn,
79 typename ContainerOut::value_type>::value,
80 "ContainerOut can not take values of type ContainerIn as elements.");
81 ContainerOut result;
82 if (size_of_cont(xs) < length)
83 return result;
84 internal::prepare_container(result, size_of_cont(xs) - length);
85 auto itOut = internal::get_back_inserter(result);
86 for (std::size_t idx = 0; idx <= size_of_cont(xs) - length; ++idx)
87 {
88 *itOut = get_segment(idx, idx + length, xs);
89 }
90 return result;
91 }
92
93 // API search type: carthesian_product_with_where : (((a, b) -> c), ((a -> b), Bool), [a], [b]) -> [c]
94 // fwd bind count: 3
95 // carthesian_product_with_where(make_pair, always(true), "ABC", "XY")
96 // == [(A,X),(A,Y),(B,X),(B,Y),(C,X),(C,Y)]
97 // same as (in Haskell):
98 // [ f x y | x <- xs, y <- ys, pred x y ]
99 // same as (in pseudo SQL):
100 // SELECT f(xs.x, ys.y)
101 // FROM xs, ys
102 // WHERE pred(xs.x, ys.y);
103 template <typename F, typename Pred, typename Container1, typename Container2>
carthesian_product_with_where(F f,Pred pred,const Container1 & xs,const Container2 & ys)104 auto carthesian_product_with_where(F f,
105 Pred pred,
106 const Container1& xs,
107 const Container2& ys)
108 {
109 using X = typename Container1::value_type;
110 using Y = typename Container2::value_type;
111 using FOut = internal::invoke_result_t<F, X, Y>;
112 using ContainerOut = std::vector<std::decay_t<FOut>>;
113
114 ContainerOut result;
115 auto itOut = internal::get_back_inserter(result);
116 for (const auto& x : xs)
117 {
118 for (const auto& y : ys)
119 {
120 if (internal::invoke(pred, x, y))
121 {
122 itOut = f(x, y);
123 }
124 }
125 }
126 return result;
127 }
128
129 // API search type: carthesian_product_with : (((a, b) -> c), [a], [b]) -> [c]
130 // fwd bind count: 2
131 // carthesian_product_with(make_pair, "ABC", "XY")
132 // == [(A,X),(A,Y),(B,X),(B,Y),(C,X),(C,Y)]
133 // same as (in Haskell):
134 // [ f x y | x <- xs, y <- ys ]
135 // same as (in pseudo SQL):
136 // SELECT f(xs.x, ys.y)
137 // FROM xs, ys;
138 template <typename F, typename Container1, typename Container2>
carthesian_product_with(F f,const Container1 & xs,const Container2 & ys)139 auto carthesian_product_with(F f, const Container1& xs, const Container2& ys)
140 {
141 auto always_true_x_y = [](const auto&, const auto&) { return true; };
142 return carthesian_product_with_where(f, always_true_x_y, xs, ys);
143 }
144
145 // API search type: carthesian_product_where : (((a, b) -> Bool), [a], [b]) -> [(a, b)]
146 // fwd bind count: 2
147 // carthesian_product_where(always(true), "ABC", "XY")
148 // == [(A,X),(A,Y),(B,X),(B,Y),(C,X),(C,Y)]
149 // same as (in Haskell):
150 // [ (x, y) | x <- xs, y <- ys, pred x y ]
151 // same as (in pseudo SQL):
152 // SELECT (xs.x, ys.y)
153 // FROM xs, ys
154 // WHERE pred(xs.x, ys.y);
155 template <typename Pred, typename Container1, typename Container2>
carthesian_product_where(Pred pred,const Container1 & xs,const Container2 & ys)156 auto carthesian_product_where(Pred pred,
157 const Container1& xs, const Container2& ys)
158 {
159 auto make_res_pair = [](const auto& x, const auto& y)
160 {
161 return std::make_pair(x, y);
162 };
163 return carthesian_product_with_where(make_res_pair, pred, xs, ys);
164 }
165
166 // API search type: carthesian_product : ([a], [b]) -> [(a, b)]
167 // fwd bind count: 1
168 // carthesian_product("ABC", "XY")
169 // == [(A,X),(A,Y),(B,X),(B,Y),(C,X),(C,Y)]
170 // same as (in Haskell):
171 // [ (x, y) | x <- xs, y <- ys ]
172 // same as (in pseudo SQL):
173 // SELECT (xs.x, ys.y)
174 // FROM xs, ys;
175 template <typename Container1, typename Container2>
carthesian_product(const Container1 & xs,const Container2 & ys)176 auto carthesian_product(const Container1& xs, const Container2& ys)
177 {
178 auto make_res_pair = [](const auto& x, const auto& y)
179 {
180 return std::make_pair(x, y);
181 };
182 auto always_true_x_y = [](const auto&, const auto&) { return true; };
183 return carthesian_product_with_where(
184 make_res_pair, always_true_x_y, xs, ys);
185 }
186
187
188 namespace internal
189 {
190 // productN :: Int -> [a] -> [[a]]
191 // productN n = foldr go [[]] . replicate n
192 // where go elems acc = [x:xs | x <- elems, xs <- acc]
193 template <typename T>
helper_carthesian_product_n_idxs(std::size_t power,const std::vector<T> & xs)194 std::vector<std::vector<T>> helper_carthesian_product_n_idxs
195 (std::size_t power, const std::vector<T>& xs)
196 {
197 static_assert(std::is_same<T, std::size_t>::value,
198 "T must be std::size_t");
199 typedef std::vector<T> Vec;
200 typedef std::vector<Vec> VecVec;
201 if (power == 0)
202 return VecVec();
203 auto go = [](const Vec& elems, const VecVec& acc)
204 {
205 VecVec result;
206 for (const T& x : elems)
207 {
208 for (const Vec& tail : acc)
209 {
210 result.push_back(append(Vec(1, x), tail));
211 }
212 }
213 return result;
214 };
215 return fold_right(go, VecVec(1), replicate(power, xs));
216 }
217 }
218
219 // API search type: carthesian_product_n : (Int, [a]) -> [[a]]
220 // fwd bind count: 1
221 // Returns the product set with a given power.
222 // carthesian_product_n(2, "ABCD")
223 // == AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
224 template <typename ContainerIn,
225 typename T = typename ContainerIn::value_type,
226 typename ContainerOut = std::vector<ContainerIn>>
carthesian_product_n(std::size_t power,const ContainerIn & xs_in)227 ContainerOut carthesian_product_n(std::size_t power, const ContainerIn& xs_in)
228 {
229 if (power == 0)
230 return ContainerOut(1);
231 std::vector<T> xs = convert_container<std::vector<T>>(xs_in);
232 auto idxs = all_idxs(xs);
233 auto result_idxss = internal::helper_carthesian_product_n_idxs(power, idxs);
234 typedef typename ContainerOut::value_type ContainerOutInner;
235 auto to_result_cont = [&](const std::vector<std::size_t>& indices)
236 {
237 return convert_container_and_elems<ContainerOutInner>(
238 elems_at_idxs(indices, xs));
239 };
240 return transform(to_result_cont, result_idxss);
241 }
242
243 // API search type: permutations : (Int, [a]) -> [[a]]
244 // fwd bind count: 1
245 // Generate all possible permutations with a given power.
246 // permutations(2, "ABCD") == AB AC AD BA BC BD CA CB CD DA DB DC
247 template <typename ContainerIn,
248 typename T = typename ContainerIn::value_type,
249 typename ContainerOut = std::vector<ContainerIn>>
permutations(std::size_t power,const ContainerIn & xs_in)250 ContainerOut permutations(std::size_t power, const ContainerIn& xs_in)
251 {
252 if (power == 0)
253 return ContainerOut(1);
254 std::vector<T> xs = convert_container<std::vector<T>>(xs_in);
255 auto idxs = all_idxs(xs);
256 typedef std::vector<std::size_t> idx_vec;
257 auto result_idxss = keep_if(all_unique<idx_vec>,
258 internal::helper_carthesian_product_n_idxs(power, idxs));
259 typedef typename ContainerOut::value_type ContainerOutInner;
260 auto to_result_cont = [&](const std::vector<std::size_t>& indices)
261 {
262 return convert_container_and_elems<ContainerOutInner>(
263 elems_at_idxs(indices, xs));
264 };
265 return transform(to_result_cont, result_idxss);
266 }
267
268 // API search type: combinations : (Int, [a]) -> [[a]]
269 // fwd bind count: 1
270 // Generate all possible combinations with a given power.
271 // combinations(2, "ABCD") == AB AC AD BC BD CD
272 template <typename ContainerIn,
273 typename T = typename ContainerIn::value_type,
274 typename ContainerOut = std::vector<ContainerIn>>
combinations(std::size_t power,const ContainerIn & xs_in)275 ContainerOut combinations(std::size_t power, const ContainerIn& xs_in)
276 {
277 if (power == 0)
278 return ContainerOut(1);
279 std::vector<T> xs = convert_container<std::vector<T>>(xs_in);
280 auto idxs = all_idxs(xs);
281 typedef std::vector<std::size_t> idx_vec;
282 auto result_idxss = keep_if(is_strictly_sorted<idx_vec>,
283 internal::helper_carthesian_product_n_idxs(power, idxs));
284 typedef typename ContainerOut::value_type ContainerOutInner;
285 auto to_result_cont = [&](const std::vector<std::size_t>& indices)
286 {
287 return convert_container_and_elems<ContainerOutInner>(
288 elems_at_idxs(indices, xs));
289 };
290 return transform(to_result_cont, result_idxss);
291 }
292
293 // API search type: combinations_with_replacement : (Int, [a]) -> [[a]]
294 // fwd bind count: 1
295 // Generate all possible combinations using replacement with a given power.
296 // combinations_with_replacement(2, "ABCD") == AA AB AC AD BB BC BD CC CD DD
297 template <typename ContainerIn,
298 typename T = typename ContainerIn::value_type,
299 typename ContainerOut = std::vector<ContainerIn>>
combinations_with_replacement(std::size_t power,const ContainerIn & xs_in)300 ContainerOut combinations_with_replacement(std::size_t power,
301 const ContainerIn& xs_in)
302 {
303 if (power == 0)
304 return ContainerOut(1);
305 std::vector<T> xs = convert_container<std::vector<T>>(xs_in);
306 auto idxs = all_idxs(xs);
307 typedef std::vector<std::size_t> idx_vec;
308 auto result_idxss = keep_if(is_sorted<idx_vec>,
309 internal::helper_carthesian_product_n_idxs(power, idxs));
310 typedef typename ContainerOut::value_type ContainerOutInner;
311 auto to_result_cont = [&](const std::vector<std::size_t>& indices)
312 {
313 return convert_container_and_elems<ContainerOutInner>(
314 elems_at_idxs(indices, xs));
315 };
316 return transform(to_result_cont, result_idxss);
317 }
318
319 // API search type: power_set : [a] -> [[a]]
320 // fwd bind count: 0
321 // Return the set of all subsets of xs_in,
322 // including the empty set and xs_in itself.
323 // power_set("xyz") == ["", "x", "y", "z", "xy", "xz", "yz", "xyz"]
324 // Also known as subsequences.
325 template <typename ContainerIn,
326 typename T = typename ContainerIn::value_type,
327 typename ContainerOut = std::vector<ContainerIn>>
power_set(const ContainerIn & xs_in)328 ContainerOut power_set(const ContainerIn& xs_in)
329 {
330 return concat(
331 generate_by_idx<std::vector<ContainerOut>>(
332 bind_1st_of_2(
333 flip(combinations<ContainerIn, T, ContainerOut>),
334 xs_in),
335 size_of_cont(xs_in) + 1));
336 }
337
338 // API search type: iterate : ((a -> a), Int, a) -> [a]
339 // fwd bind count: 2
340 // Repeatedly apply a function (n times) to a value (starting with x)
341 // and recording the outputs on its way.
342 // iterate((*2), 5, 3) = [3, 6, 12, 24, 48]
343 // = [3, f(3), f(f(3)), f(f(f(3))), f(f(f(f(3))))]
344 template <typename F,
345 typename T,
346 typename ContainerOut = std::vector<T>>
iterate(F f,std::size_t size,const T & x)347 ContainerOut iterate(F f, std::size_t size, const T& x)
348 {
349 ContainerOut result;
350 if (size == 0)
351 return result;
352 internal::prepare_container(result, size + 1);
353 auto it_out = internal::get_back_inserter(result);
354 T current = x;
355 *it_out = current;
356 for (std::size_t i = 1; i < size; ++i)
357 {
358 current = internal::invoke(f, current);
359 *it_out = current;
360 }
361 return result;
362 }
363
364 // API search type: iterate_maybe : ((a -> Maybe a), a) -> [a]
365 // fwd bind count: 1
366 // Repeatedly apply a function to a value (starting with x)
367 // and recording the outputs on its way.
368 // Stops when the function returns nothing.
369 // iterate_maybe(next_collats_val, 5) = [5, 16, 8, 4, 2, 1]
370 template <typename F,
371 typename T,
372 typename ContainerOut = std::vector<T>>
iterate_maybe(F f,const T & x)373 ContainerOut iterate_maybe(F f, const T& x)
374 {
375 ContainerOut result;
376 auto it_out = internal::get_back_inserter(result);
377 maybe<T> current(x);
378 while (current.is_just())
379 {
380 *it_out = current.unsafe_get_just();
381 current = internal::invoke(f, current.unsafe_get_just());
382 }
383 return result;
384 }
385
386 // API search type: adjacent_difference_by : [a] -> [a]
387 // fwd bind count: 1
388 // Computes the differences between the second
389 // and the first of each adjacent pair of elements of the sequence
390 // using a binary function.
391 // adjacent_difference_by([0,4,1,2,5]) == [0,4,-3,1,3]
392 template <typename ContainerIn, typename F>
adjacent_difference_by(F f,const ContainerIn & xs)393 auto adjacent_difference_by(F f, const ContainerIn& xs)
394 {
395 using X = typename ContainerIn::value_type;
396 using TOut = internal::invoke_result_t<F, X, X>;
397 using ContainerOut = std::vector<std::decay_t<TOut>>;
398
399 ContainerOut result;
400
401 using std::begin;
402 using std::end;
403 internal::prepare_container(result, size_of_cont(xs));
404 std::adjacent_difference(begin(xs), end(xs), back_inserter(result), f);
405 return result;
406 }
407
408 // API search type: adjacent_difference : [a] -> [a]
409 // fwd bind count: 0
410 // Computes the differences between the second
411 // and the first of each adjacent pair of elements of the sequence.
412 // adjacent_difference([0,4,1,2,5]) == [0,4,-3,1,3]
413 template <typename Container>
adjacent_difference(const Container & xs)414 Container adjacent_difference(const Container& xs)
415 {
416 return adjacent_difference_by(
417 std::minus<typename Container::value_type>(), xs);
418 }
419
420 // API search type: rotate_left : [a] -> [a]
421 // fwd bind count: 0
422 // Removes the first element and appends it to the back.
423 // rotate_left("xyz") == "yzx"
424 template <typename Container>
rotate_left(const Container & xs)425 Container rotate_left(const Container& xs)
426 {
427 if (is_empty(xs))
428 return xs;
429 Container ys;
430 auto size = size_of_cont(xs);
431 internal::prepare_container(ys, size);
432 auto it = std::begin(xs);
433 auto it_out = internal::get_back_inserter(ys);
434 ++it;
435 while (it != std::end(xs))
436 {
437 *it_out = *it;
438 ++it;
439 }
440 *it_out = xs.front();
441 return ys;
442 }
443
444 // API search type: rotate_right : [a] -> [a]
445 // fwd bind count: 0
446 // Removes the last element and prepends it to the front.
447 // rotate_right("xyz") == "zxy"
448 template <typename Container>
rotate_right(const Container & xs)449 Container rotate_right(const Container& xs)
450 {
451 return reverse(rotate_left(reverse(xs)));
452 }
453
454 // API search type: rotations_left : [a] -> [[a]]
455 // fwd bind count: 0
456 // Returns all possible rotations using rotate_left.
457 // rotations_left("abcd") == ["abcd", "bcda", "cdab", "dabc"]
458 template <typename ContainerIn,
459 typename T = typename ContainerIn::value_type,
460 typename ContainerOut = std::vector<ContainerIn>>
rotations_left(const ContainerIn & xs_in)461 ContainerOut rotations_left(const ContainerIn& xs_in)
462 {
463 return iterate(rotate_left<ContainerIn>, size_of_cont(xs_in), xs_in);
464 }
465
466 // API search type: rotations_right : [a] -> [[a]]
467 // fwd bind count: 0
468 // Returns all possible rotations using rotate_right.
469 // rotations_right("abcd") == ["abcd", "dabc", "cdab", "bcda"]
470 template <typename ContainerIn,
471 typename T = typename ContainerIn::value_type,
472 typename ContainerOut = std::vector<ContainerIn>>
rotations_right(const ContainerIn & xs_in)473 ContainerOut rotations_right(const ContainerIn& xs_in)
474 {
475 return iterate(rotate_right<ContainerIn>, size_of_cont(xs_in), xs_in);
476 }
477
478 // API search type: fill_left : (a, Int, [a]) -> [a]
479 // fwd bind count: 2
480 // Right-align a sequence.
481 // fill_left(0, 6, [1,2,3,4]) == [0,0,1,2,3,4]
482 // Also known as pad_left.
483 template <typename Container,
484 typename T = typename Container::value_type>
485 Container fill_left(const T& x, std::size_t min_size, const Container& xs)
486 {
487 if (min_size <= size_of_cont(xs))
488 return xs;
489 return append(replicate<T, Container>(min_size - size_of_cont(xs), x), xs);
490 }
491
492 // API search type: fill_right : (a, Int, [a]) -> [a]
493 // fwd bind count: 2
494 // Left-align a sequence.
495 // fill_right(0, 6, [1,2,3,4]) == [1,2,3,4,0,0]
496 template <typename Container,
497 typename T = typename Container::value_type>
498 Container fill_right(const T& x, std::size_t min_size, const Container& xs)
499 {
500 if (min_size <= size_of_cont(xs))
501 return xs;
502 return append(xs, replicate<T, Container>(min_size - size_of_cont(xs), x));
503 }
504
505 // API search type: inits : [a] -> [[a]]
506 // fwd bind count: 0
507 // Generate all possible segments of xs that include the first element.
508 // inits([0,1,2,3]) == [[],[0],[0,1],[0,1,2],[0,1,2,3]]
509 template <typename ContainerIn,
510 typename T = typename ContainerIn::value_type,
511 typename ContainerOut = std::vector<ContainerIn>>
inits(const ContainerIn & xs)512 ContainerOut inits(const ContainerIn& xs)
513 {
514 ContainerOut result;
515 std::size_t xs_size = size_of_cont(xs);
516 internal::prepare_container(result, xs_size + 1);
517 auto it_out = internal::get_back_inserter(result);
518 for (std::size_t i = 0; i <= xs_size; ++i)
519 *it_out = get_segment(0, i, xs);
520 return result;
521 }
522
523 // API search type: tails : [a] -> [[a]]
524 // fwd bind count: 0
525 // Generate all possible segments of xs that include the last element.
526 // tails([0,1,2,3]) == [[0,1,2,3],[1,2,3],[2,3],[3],[]]
527 template <typename ContainerIn,
528 typename T = typename ContainerIn::value_type,
529 typename ContainerOut = std::vector<ContainerIn>>
tails(const ContainerIn & xs)530 ContainerOut tails(const ContainerIn& xs)
531 {
532 ContainerOut result;
533 std::size_t xs_size = size_of_cont(xs);
534 internal::prepare_container(result, xs_size + 1);
535 auto it_out = internal::get_back_inserter(result);
536 for (std::size_t i = 0; i <= xs_size; ++i)
537 *it_out = get_segment(i, xs_size, xs);
538 return result;
539 }
540
541 } // namespace fplus
542