{"id":1145,"date":"2015-07-01T12:54:37","date_gmt":"2015-07-01T19:54:37","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=1145"},"modified":"2015-07-01T23:09:45","modified_gmt":"2015-07-02T06:09:45","slug":"exercising-ranges-part-5","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=1145","title":{"rendered":"Exercising Ranges (part 5)"},"content":{"rendered":"

(Start at the beginning of the series<\/a> if you want more context.)<\/p>\n

Generalising iota<\/code><\/strong><\/p>\n

To pretty-print a reversible polynomial, we need to provide for reversibility of iota<\/code>. So what is iota<\/code>? It makes a range by repeatedly incrementing a value. What if instead of increment, we use an arbitrary function? We could do this with generate_n<\/code>:<\/p>\n

\r\ntemplate \r\nstd::string to_string_reverse(Rng&& r)\r\n{\r\n  auto s = ranges::size(r);\r\n  auto powers = ranges::view::generate_n(\r\n      [s] () mutable { return --s; }, s);\r\n  return detail::to_string(\r\n      ranges::view::zip(ranges::view::reverse(std::forward(r)), \r\n                        powers));\r\n}\r\n<\/pre>\n
But this isn’t quite as clean as it could be: the lambda mutates state. An alternative is found in the Haskell Prelude:<\/p>\n
\r\niterate :: (a -> a) -> a -> [a] \r\n<\/pre>\n
iterate<\/code> applies a function repeatedly to an argument, feeding the result of the last iteration to the input of the next one. It’s very similar to generate<\/code>, and we can write both iterate<\/code> and iterate_n<\/code>. The view takes a function and an initial value, and produces the sequence:<\/p>\n
[latex] x, f(x), f(f(x)), f(f(f(x))), … [\/latex]<\/p>\n
Here’s the C++ for the skeleton of iterate_view<\/code>:<\/p>\n
\r\ntemplate\r\nstruct iterate_view\r\n  : view_facade, infinite>\r\n{\r\nprivate:\r\n  friend struct range_access;\r\n  using result_t = concepts::Function::result_t;\r\n  semiregular_t gen_;\r\n  semiregular_t val_;\r\n  ...\r\n  explicit iterate_view(G g, T&& t)\r\n    : gen_(std::move(g)), val_(std::move(t))\r\n  {}\r\n  ...\r\n};\r\n<\/pre>\n
The cursor is easily written just like generate<\/code>‘s cursor: next()<\/code> caches a new value, and current()<\/code> returns it. Like generate<\/code>, the view can only be traversed once, so the cached value is kept in the view itself rather than the iterator. And there is no end cursor.<\/p>\n
\r\nstruct cursor\r\n{\r\n  iterate_view *view_;\r\n  ...\r\n  result_t current() const\r\n  {\r\n    return view_->val_;\r\n  }\r\n  void next()\r\n  {\r\n    view_->next();\r\n  }\r\n};\r\nvoid next()\r\n{\r\n  val_ = gen_(val_);\r\n}\r\n<\/pre>\n
For iterate_n<\/code>, the approach is almost identical, except that next()<\/code> decrements a count, and size()<\/code> is also provided. Using iterate_n<\/code>, we can generate a decreasing sequence and use it in the reverse print function for a polynomial, which we know is a SizedRange<\/code>.<\/p>\n
\r\ntemplate \r\nstd::string to_string_reverse(Rng&& r)\r\n{\r\n  auto s = ranges::size(r);\r\n  auto powers = ranges::view::iterate_n(\r\n      [] (auto i) { return i - 1; }, s-1, s);\r\n  return detail::to_string(\r\n      ranges::view::zip(ranges::view::reverse(std::forward(r)), \r\n                        powers));\r\n}\r\n<\/pre>\n
As for iterate<\/code> itself, it’s potentially useful in lots more places. The obvious use cases (and test cases) are mathematical in nature, for instance my test case using the Collatz conjecture (aka Ulam conjecture, 3n+1 conjecture) sequence starting with 27<\/a>:<\/p>\n
\r\nint collatz(int n)\r\n{\r\n  if (n & 1) return 3*n+1;\r\n  return n>>1;\r\n}\r\n\r\nDEF_TEST(Collatz27, Iterate)\r\n{\r\n  auto m = view::iterate(collatz, 27)\r\n    | view::take_while([] (int n) { return n != 1; });\r\n  EXPECT(ranges::find(m, 9232) != ranges::end(m));\r\n  return true;\r\n}\r\n<\/pre>\n
But there are also plenty of applications in other code, where we are updating the state of something based on its previous state: iterate<\/code> separates the loop code and allows us to write a clean function that simply produces a new state from an old state. This is useful for games and simulations of all kinds. So iterate<\/code> is a useful addition to the range views.<\/p>\n
Now we can pretty-print polynomials properly, in the next part<\/a> I’m going to take on the trickier subject of how to multiply them.<\/p>\n","protected":false},"excerpt":{"rendered":"
(Start at the beginning of the series if you want more context.) Generalising iota To pretty-print a reversible polynomial, we need to provide for reversibility of iota. So what is iota? It makes a range by repeatedly incrementing a value. What if instead of increment, we use an arbitrary function?…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22,8],"tags":[],"class_list":["post-1145","post","type-post","status-publish","format-standard","hentry","category-cpp","category-programming"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1145"}],"version-history":[{"count":10,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1145\/revisions"}],"predecessor-version":[{"id":1192,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1145\/revisions\/1192"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}