![\"timeline\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/04\/timeline.png\")
<\/p>\n
Today, I’m writing about the seven new algorithms. Here are they.<\/p>\n
std::<\/span>for_each_n\r\n\r\nstd::<\/span>exclusive_scan\r\nstd::<\/span>inclusive_scan\r\n\r\nstd::<\/span>transform_exclusive_scan\r\nstd::<\/span>transform_inclusive_scan\r\n\r\nstd::<\/span>parallel::<\/span>reduce\r\nstd::<\/span>parallel::<\/span>transform_reduce\r\n<\/pre>\n<\/div>\n <\/p>\n
Besides std::for_each_n<\/span> these names are pretty unusual. So let me make a short detour and write about Haskell.<\/p>\n<\/p>\nA short detour<\/h2>\n
To make the long story short. All new functions have a pendant in the pure functional language Haskell.<\/p>\n
\n- for_each_n<\/span> is called map <\/span>in Haskell.<\/li>\n
- exclusive_scan<\/span> and inclusive_scan<\/span> are called scanl<\/span> and scanl1<\/span> in Haskell.<\/li>\n
- transform_exclusive_scan<\/span> and transform_inclusive_scan<\/span> is a composition of the Haskell functions map<\/span> and scanl<\/span> or scanl1<\/span>.<\/li>\n
- reduce <\/span>is called foldl <\/span>or foldl1 <\/span>in Haskell.<\/li>\n
- transform_reduce<\/span> is a composition of the Haskell functions map <\/span>and foldl <\/span>or foldl1<\/span>.<\/li>\n<\/ul>\n
Before I show you Haskell in action, let me describe the different functions.<\/p>\n
\n- map <\/span>applies a function to a list.<\/li>\n
- foldl <\/span>and foldl1 <\/span>apply a binary operation to a list and reduces the list to a value. foldl <\/span>needs contrary to foldl1 <\/span>an initial value.<\/li>\n
- scanl <\/span>and scanl1 <\/span>apply the same strategy such as foldl <\/span>and foldl1, <\/span>but they produce all intermediate values. So you get back a list.<\/li>\n
- foldl<\/span>, foldl1<\/span>, scanl<\/span>, and scanl1<\/span> start their job from the left.<\/li>\n<\/ul>\n
Now comes the action. Here is Haskell’s interpreter shell.<\/p>\n
![\"newAlgorithmHaskell\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/05\/newAlgorithmHaskell.png\")
<\/p>\n
(1) and (2) define a list of integers and a list of strings. In (3), I apply the lambda function (\\a -> a * <\/span>a) to the list of ints<\/span>. (4) and (5) are more sophisticated. The expression (4) multiplies (*) all pairs of integers, starting with 1 as a neutral multiplication element. Expression (5) does the corresponding for the addition. The expressions (6), (7), and (9) are quite challenging to read for the imperative eye. You have to read them from right to left. scanl1 (+) . map(\\a -> length a (7)<\/span> is a function composition. The dot (.) symbol composes the two functions. The first function maps each element to its length. The second function adds the list of lengths together. (9) is similar to 7. The difference is that foldl <\/span>produces one value and requires an initial element. This is 0. Now, the expression (8) should be readable. The expression successively joins two strings with the “:<\/span>” character. <\/p>\nYou wonder why I write in a C++ blog so much challenging stuff about Haskell. That is for two good reasons. First, you know the history of C++ functions. And second, it’s a lot easier to understand the C++ function if you compare them with the Haskell pendants.<\/p>\n
So, let’s finally start with C++.<\/p>\n
The seven new algorithms<\/h2>\n
I promised it may become a little bit difficult to read.<\/p>\n
<\/p>\n
\n\/\/ newAlgorithm.cpp<\/span>\r\n\r\n#include <hpx\/hpx_init.hpp><\/span>\r\n#include <hpx\/hpx.hpp><\/span>\r\n#include <hpx\/include\/parallel_numeric.hpp><\/span>\r\n#include <hpx\/include\/parallel_algorithm.hpp><\/span>\r\n#include <hpx\/include\/iostreams.hpp><\/span>\r\n\r\n#include <string><\/span>\r\n#include <vector><\/span>\r\n\r\n\r\nint<\/span> hpx_main<\/span>(){\r\n \r\n hpx::<\/span>cout <<<\/span> hpx::<\/span>endl;\r\n \r\n \/\/ for_each_n<\/span>\r\n \r\n std::<\/span>vector<<\/span>int<\/span>><\/span> intVec{1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>, 10<\/span>}; \/\/ 1<\/span>\r\n hpx::<\/span>parallel::<\/span>for_each_n(hpx::<\/span>parallel::<\/span>execution::<\/span>par, \/\/ 2<\/span>\r\n intVec.begin(), 5<\/span>, [](int<\/span>&<\/span> arg){ arg *=<\/span> arg; });\r\n \r\n hpx::<\/span>cout <<<\/span> \"for_each_n: \"<\/span>;\r\n for<\/span> (auto<\/span> v:<\/span> intVec) hpx::<\/span>cout <<<\/span> v <<<\/span> \" \"<\/span>;\r\n hpx::<\/span>cout <<<\/span> \"<\/span>\\n\\n<\/span>\"<\/span>;\r\n \r\n \/\/ exclusive_scan and inclusive_scan<\/span>\r\n std::<\/span>vector<<\/span>int<\/span>><\/span> resVec{1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>};\r\n hpx::<\/span>parallel::<\/span>exclusive_scan(hpx::<\/span>parallel::<\/span>execution::<\/span>par, \/\/ 3<\/span>\r\n resVec.begin(), resVec.end(), resVec.begin(), 1<\/span>,\r\n [](int<\/span> fir, int<\/span> sec){ return<\/span> fir *<\/span> sec; });\r\n \r\n hpx::<\/span>cout <<<\/span> \"exclusive_scan: \"<\/span>;\r\n for<\/span> (auto<\/span> v:<\/span> resVec) hpx::<\/span>cout <<<\/span> v <<<\/span> \" \"<\/span>;\r\n hpx::<\/span>cout <<<\/span> hpx::<\/span>endl; \r\n \r\n std::<\/span>vector<<\/span>int<\/span>><\/span> resVec2{1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>};\r\n \r\n hpx::<\/span>parallel::<\/span>inclusive_scan(hpx::<\/span>parallel::<\/span>execution::<\/span>par, \/\/ 5 <\/span>\r\n resVec2.begin(), resVec2.end(), resVec2.begin(), \r\n [](int<\/span> fir, int<\/span> sec){ return<\/span> fir *<\/span> sec; }, 1<\/span>);\r\n \r\n hpx::<\/span>cout <<<\/span> \"inclusive_scan: \"<\/span>;\r\n for<\/span> (auto<\/span> v:<\/span> resVec2) hpx::<\/span>cout <<<\/span> v <<<\/span> \" \"<\/span>;\r\n hpx::<\/span>cout <<<\/span> \"<\/span>\\n\\n<\/span>\"<\/span>;\r\n \r\n \/\/ transform_exclusive_scan and transform_inclusive_scan<\/span>\r\n std::<\/span>vector<<\/span>int<\/span>><\/span> resVec3{1<\/span>, 2<\/span>, 3<\/span>, 4<\/span>, 5<\/span>, 6<\/span>, 7<\/span>, 8<\/span>, 9<\/span>};\r\n std::<\/span>vector<<\/span>int<\/span>><\/span> resVec4(resVec3.size()); \r\n hpx::<\/span>parallel::<\/span>transform_exclusive_scan(hpx::<\/span>parallel::<\/span>execution::<\/span>par, \/\/ 6<\/span>\r\n resVec3.begin(), resVec3.end(), \r\n resVec4.begin(), 0<\/span>,\r\n [](int<\/span> fir, int<\/span> sec){ return<\/span> fir +<\/span> sec; },\r\n [](int<\/span> arg){ return<\/span> arg *=<\/span> arg; });\r\n \r\n hpx::<\/span>cout <<<\/span> \"transform_exclusive_scan: \"<\/span>;\r\n for<\/span> (auto<\/span> v:<\/span> resVec4) hpx::<\/span>cout <<<\/span> v <<<\/span> \" \"<\/span>;\r\n hpx::<\/span>cout <<<\/span> hpx::<\/span>endl;\r\n \r\n std::<\/span>vector<<\/span>std::<\/span>string><\/span> strVec{\"Only\"<\/span>,\"for\"<\/span>,\"testing\"<\/span>,\"purpose\"<\/span>}; \/\/ 7<\/span>\r\n std::<\/span>vector<<\/span>int<\/span>><\/span> resVec5(strVec.size());\r\n \r\n hpx