{"id":5168,"date":"2017-02-05T17:03:48","date_gmt":"2017-02-05T17:03:48","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/the-new-ranges-library\/"},"modified":"2023-06-26T12:24:26","modified_gmt":"2023-06-26T12:24:26","slug":"the-new-ranges-library","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/the-new-ranges-library\/","title":{"rendered":"The New Ranges Library"},"content":{"rendered":"

A small-time jump, and we are in the year 2020. C++ will get – as far as the future is predictable – the new ranges library. Thanks to Eric Nieblers library, working with the Standard Template Library (STL) will become more comfortable and powerful.<\/p>\n

 <\/p>\n

<\/p>\n

 <\/p>\n

Much more comfortable because the algorithm of the STL can directly work on the containers and need no begin and end iterator. We get more powerful with the ranges library lazy evaluation, improved function composition, and range comprehension in C++20.<\/p>\n

Firstly, let me talk about the point more comfortably.<\/p>\n

More comfortable<\/h2>\n

Iterators are the glue between the generic algorithms and containers of the STL. Therefore, each container returns on request an iterator pointing to the first element and an iterator pointing just behind the last element of the container. The half-open range interval defines the range of the algorithm. Thanks to the ranges library, you no longer need a half-open interval in C++20. You can directly apply the algorithm to the container:<\/p>\n

 <\/p>\n

<\/p>\n

\n
std::vector<int<\/span>> vec{2, 5, 3, 1, 4};\r\nstd::sort(vec.begin(), vec.end());   \r\nstd::sort(vec);                   \/\/ C++20
<\/span>\r\n<\/pre>\n<\/div>\n
 <\/p>\n
Now, I will write about the functional features in the ranges library.<\/p>\n<\/p>\n
Lazy evaluation<\/h2>\n
Haskell is, by default, lazy (see Recursion, List Manipulation, and Lazy Evaluation<\/a>). Due to lazy evaluation, you can define in the Haskell algorithm on infinite data structures if you only ask for a finite number of elements at runtime. Therefore, you can separate the algorithm for calculating the infinite data structure from its usage.<\/p>\n
Lazy evaluation is one of the characteristics of functional programming. With C++20, we will get it. Thanks to lazy evaluation, I can directly translate the Haskell code in the example into C++:<\/p>\n
 <\/p>\n
<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26<\/pre>\n<\/td>\n
\n
\/\/ lazyEvaluation.cpp<\/span>\r\n\r\n#include <range\/v3\/all.hpp><\/span>\r\n#include <iostream><\/span>\r\n#include <tuple><\/span>\r\n\r\nusing<\/span> namespace<\/span> ranges;\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  \/\/ take 5 [1..]  -- [1,2,3,4,5]<\/span>\r\n\r\n  auto<\/span> num = view::take(view::ints(1), 5);\r\n  ranges::for_each(num, [](int<\/span> i){ std::cout << i << \" \"<\/span>; });\r\n\r\n  std::cout << \"\\n\\n\"<\/span>;\r\n\r\n  auto<\/span> pairs= view::zip_with([](int<\/span> i, char<\/span> c){ return<\/span> std::make_pair(i, c); } , view::ints(0), \"ranges\"<\/span>);\r\n\r\n  ranges::for_each(pairs, [](std::pair<int<\/span>,char<\/span>> p){ std::cout << \"(\"<\/span> <<  p.first << \":\"<\/span> << p.second << \")\"<\/span>; });\r\n\r\n  std::cout << \"\\n\\n\"<\/span>;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
view::ints(1)<\/span> in line 15 creates an infinite sequence of numbers starting with 1. The key is that I’m only asking for 5 of them. Using a lambda function, the numbers will be displayed in the following for_each loop. Admittedly, that is not so elegant. Firstly, I can implement the algorithm more elegantly with function composition: auto num= view::ints(1) | view::take(5)<\/span>. The details will follow in a few seconds. Secondly, the upcoming C++20 standard will support the output of ranges with the range-based for-loop: for (n: num) std::cout << num << ” “.<\/span><\/p>\n
The functional world-known function view::zip_with <\/span>takes lists and a lambda function and zips the list with the help of a lambda function to a new list. Therefore, the lambda function in line 22 zips the infinite sequence of numbers starting with 0 with the finite string “ranges”.<\/span> The result is a finite tuple. So you can refer to elements of the pairs by using the first<\/span> or second.<\/span><\/p>\n
\"lazy\"<\/p>\n
Function composition<\/h2>\n
Function composition in Haskell feels like putting Lego stones together. The newly created functions express their functionality very concisely and are readable for the used programmer, like prose. In Haskell, the power of function composition is based on three pillars:<\/p>\n
Haskell’s functions<\/p>\n
    \n
  1. perform one task,<\/strong><\/li>\n
  2. use the list as the essential data structure <\/strong>and<\/li>\n
  3. use the (.) for function composition.<\/strong><\/li>\n<\/ol>\n
    The story is similar to the ranges library. The library has a rich set of functions<\/a>. These functions are inspired by Haskell, which works on the key data structure range and uses the, from the Unix shell or Windows PowerShell known, pipe symbol (|) for function composition.<\/p>\n
    Once more, I show how you can implement Haskell code in C++20:<\/p>\n
     <\/p>\n
    <\/p>\n
    \n\n\n\n
    \n
     1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35<\/pre>\n<\/td>\n
    		\n
    \/\/ functionCompositionRanges.cpp<\/span>\r\n\r\n#include <range\/v3\/all.hpp><\/span>\r\n#include <numeric><\/span>\r\n#include <iostream><\/span>\r\n\r\nusing<\/span> namespace<\/span> ranges;\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  \/\/ odds= takeWhile (< 1000) . filter odd . map (^2)<\/span>\r\n  \/\/ odds [1..]                 -- [1,9,25, ... , 841,961]<\/span>\r\n\r\n  auto<\/span> odds= view::transform([](int<\/span> i){ return<\/span> i*i;} ) |\r\n             view::remove_if([](int<\/span> i){ return<\/span> i % 2 == 0; } ) |\r\n             view::take_while([](int<\/span> i){ return<\/span> i < 1000;} );\r\n  auto<\/span> oddNumbers= view::ints(1) | odds;\r\n\r\n  ranges::for_each(oddNumbers,[](int<\/span> i){ std::cout << i << \" \"<\/span>; });\r\n\r\n  std::cout << \"\\n\\n\"<\/span>;\r\n\r\n  \/\/ total= sum $ take 100 $ map (\\x -> x*x) [100..1000] -- 2318350<\/span>\r\n\r\n  auto<\/span> total= ranges::accumulate(view::ints(100, 1000) |\r\n                                 view::transform([](int<\/span> x){ return<\/span> x*x; }) |\r\n                                 view::take(100), 0);\r\n\r\n  std::cout << \"total: \"<\/span> << total << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
     <\/p>\n
    The evaluation order of function composition is in Haskell (line 13) from right to left; in C++ (lines 16 – 19) from left to right. The C++ expression in lines 27 – 29 is not so easy to digest. It accumulates (ranges::accumulate<\/span>) the first 100 numbers (view::take(100)<\/span>) from the numbers from 100 – 1000 (view::ints(100,1000<\/span>)) by mapping each number to its square (view::transform([](int x){ return x*x; }<\/span>). The start value is 0.<\/p>\n
    Here is the output of the program.<\/p>\n
    \"composition\"<\/p>\n
    Range comprehension<\/h2>\n
    List comprehension is syntactic sugar<\/a> of the sweetest kind for the functional algorithm map and filter <\/a>and allows you to create new lists at runtime. The functional programming language Miranda introduced list comprehension; Haskell made them known. It is not an accident that list comprehension looks like the mathematical notation for set comprehension because Haskell is based on mathematical concepts.<\/p>\n
    The figure compares set comprehension in Mathematics with list comprehension in Haskell.<\/p>\n
     \"setListComprehension\"<\/p>\n
    The ranges library supports range comprehension. It’s not as sweet as list comprehension, but the functionality is comparable.<\/p>\n
     <\/p>\n
    <\/p>\n
    \n\n\n\n
    \n
     1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23<\/pre>\n<\/td>\n
    		\n
    \/\/ rangeComprehension.cpp<\/span>\r\n\r\n#include <range\/v3\/all.hpp><\/span>\r\n#include <iostream><\/span>\r\n\r\nusing<\/span> namespace<\/span> ranges;\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  \/\/ odds= [ x*x | x <-[1..] , odd x  ]<\/span>\r\n  \/\/ takeWhile (<1000) odds --  -- [1,9,25, ... , 841,961]<\/span>\r\n\r\n  auto<\/span> odds= view::ints(1) | view::for_each([](int<\/span> i){ return<\/span> yield_if(i%2 == 1, i*i); });\r\n\r\n  ranges::for_each(odds | view::take_while([](int<\/span> i){ return<\/span> i < 1000; }) , [](int<\/span> i){\r\n    std::cout << i << \" \"<\/span>;\r\n  });\r\n\r\n  std::cout << \"\\n\\n\"<\/span>;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
     <\/p>\n
    The list comprehension in Haskell (line 12) is very concise. I request the integers starting with 1(x<-[1..]<\/span>), keep the odd values (odd x<\/span>), and map them to their square (x*x<\/span>). The expression odd<\/span> corresponds to the filter function and x*x<\/span> to the map function. The list will be evaluated in line 13 as long as their elements are smaller than 1000 (takeWhile(<1000)<\/span>).<\/p>\n
    I apply the same strategy in C++. The first argument of the yield_if<\/span> function is the filter expression, and the second one is the map expression.<\/p>\n
    In the end, the output of the program.
    <\/span><\/p>\n
     \"rangeComprhension\"<\/p>\n
    If I use more generators for integers or filter expressions in a range of comprehension, the expression will become very difficult to understand. I present in the following example the Pythagorean Triple in Haskell and C++. The Pythagorean triple consists of three positive integers x<\/span>, y<\/span>, and z<\/span>, such that x2<\/sup> + y2<\/sup> = z2<\/sup><\/span>.<\/p>\n
     <\/p>\n
    <\/p>\n
    \n
    triples =[(x, y, z)|z <-[1..], x <-[1..z],y <-[x..z] ,x^2 + y^2 == z^2]\r\n\r\nauto<\/span> triples = \r\n  view::for_each(view::ints(1),[](int<\/span> z){
        return<\/span> view::for_each(view::ints(1, z),[=](int<\/span> x){\r\n      return<\/span> view::for_each(view::ints(x, z),[=](int<\/span> y){\r\n        return<\/span> yield_if(x*x + y*y == z*z, std::make_tuple(x, y, z));\r\n      });\r\n    });\r\n  });\r\n<\/pre>\n<\/div>\n
     <\/p>\n
     <\/p>\n
    The view <\/strong>algorithms, such as view::for_each<\/span> of the ranges library, are standard in that they are lightweight wrappers for the underlying range. They will only evaluate its arguments on request and can not change them. With actions<\/strong> such as (action::remove_if<\/span>), the ranges library has a bunch of additional algorithms that can change their arguments and create new ranges. Contrary to the view algorithms, the action algorithms are not lazy. They are eager.<\/p>\n
    What’s next?<\/h2>\n
    Eric Niebler used the type-traits library to make the range library’s algorithm type-safe. That is no longer necessary with C++20 because we get concepts. Now you know what I will write about in my next post<\/a>.<\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    A small-time jump, and we are in the year 2020. C++ will get – as far as the future is predictable – the new ranges library. Thanks to Eric Nieblers library, working with the Standard Template Library (STL) will become more comfortable and powerful.  <\/p>\n","protected":false},"author":21,"featured_media":5164,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[365],"tags":[508,413],"class_list":["post-5168","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-functional","tag-haskell","tag-ranges"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5168","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5168"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5168\/revisions"}],"predecessor-version":[{"id":6891,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5168\/revisions\/6891"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5164"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}