6 ms·

Lazy sequences in idiomatic C++ using iterators

39 points by jzwinck 13y ago

lelf 13y ago
This is different. They are combining streams in the original article. (‘Start with the stream of integers from 1 to infinity <…>’). Your code is take 10 mutable_spaghetti_function
- dkhenry 13y ago
  And as a trade off you get a much cleaner and more performant solution to the same contrived problem. This is where Haskell and functional coders tend to break down. Yes its mutable, but by violating that one rule you gain so much in terms of readability and performance.
  - 5hoom 13y ago
    That's one thing I've noticed with my C++ code lately is that I'm writing const absolutely everywhere. Having mutability where you need it is awesome but it is interesting to see languages like Rust where immutability is the default.
    - jzwinck 13y ago
      I have done a bit of this too. The main downside in C++ is that you end up writing a few more ternary operators than you otherwise may have. But it is nice to be able to look at the first assignment of a variable and know it is the only one.
      - 5hoom 13y ago
        Yeah it kind of feels dirty having all these mutable variables around after doing any functional programming at all. I've found using const a lot also goes hand-in-hand with raii. If a member of a class is const it must be initialized in the constructor, and it just seems to make me code a bit more "hygienically".
  - cgh 13y ago
    You are right about more performant, but how is it cleaner and more readable than this? pyth x = [(a,b,c) | a<-[1..x], b<-[1..x], c<-[1..x], (a^2)+(b^2) == (c^2)]
    - dkhenry 13y ago
      Thats not c++ code. My claim is that if you try to stay pure using C++ you end up with very very ugly code that preforms pretty poorly.
- jzwinck 13y ago
  Indeed. This is part of why I included "idiomatic" in the title here. Someone smarter than me already wrote a bit prettier iterator increment function, and using that is easy once you have the interface decided. And in C++, iterators abound, and can be used as infinite sequence generators with no difference to how they are normally used and understood. The code may be spaghetti, but I mostly just lifted it from the referenced article and solved the problems the original author brought up, namely the separation of concerns. The C++ solution to this problem will never be as beautiful as the Haskell one, but I wanted to show it doesn't have to be alienating for people who program C++ daily. C++ iterators are powerful, and can be used for a lot more than stepping through a container. We write too few of them.
zwegner 13y ago
All those if statements inside loops... would be a lot cleaner (and faster!) to just use a single goto statement: goto cont; for (; ; ++z) for (; x <= z; ++x) for (; y <= z; ++y) { if (x*x + y*y == z*z) return *this; cont: }
- jzwinck 13y ago
  I totally agree--thank you for bringing this up. I'm not sure it would be faster, but it is an interesting case for goto. I saw another proposal referencing the original article which used a trio of functions in a nice way to achieve something similar without the goto (and without the ifs). My main point was to illustrate the use of custom iterators.
  - zwegner 13y ago
    Consider me nerd-sniped. I typed the last post on my phone, but just had to bust out the laptop to check. Noticed a couple bugs I had: the for-loop initializers need to be set, and there needs to be an empty statement after the cont: label. The goto version only has one unconditional branch outside of a loop, rather than three conditional branches inside loops. Anyways, the speed difference shouldn't be too big, as the branches are pretty predictable (pretty much always not taken). Quick benchmark of the original and mine, up to the first 3000 triples: $ c++ -O3 pyth1.cpp && time ./a.out | md5 33aa33d6cad59951489757e06aeb5a15 real 0m5.492s user 0m5.484s sys 0m0.007s $ c++ -O3 pyth2.cpp && time ./a.out | md5 33aa33d6cad59951489757e06aeb5a15 real 0m4.248s user 0m4.238s sys 0m0.011s
- 5hoom 13y ago
  I'm always looking for a legitimate excuse to use a goto in my C++ code because I'm perverse. It's very rare to find one but this looks like it might be okay.
- Pxtl 13y ago
  All the crazy crap they added to C/C++, how was named loops and corresponding named break/continue not one of them?
pfultz2 13y ago
This can already be done using Linq in C++, which is range-based rather than iterator based: auto q = LINQ( from(z, boost::irange(1, std::numerical_limits<int>::max())) from(x, boost::irange(1, z)) from(y, boost::irange(1, x)) where(x*x + y*y == z*z) select(boost::fusion::make_vector(x, y, z)) ); for(auto&& x:q | linq::take(10)) std::cout << x << std::endl; Hopefully, once we get ranges in the C++ standard library, we can add list comprehension to the language, perhaps something like this: auto q = [ for (z, std::irange(1, std::numerical_limits<int>::max())) for (x, std::irange(1, z)) for (y, std::irange(1, x)) if (x*x + y*y == z*z) boost::fusion::make_vector(x, y, z) ]; for(auto&& x:q | std::take(10)) std::cout << x << std::endl;
- deleted 13y ago
  [deleted]
detrino 13y ago
A cleaner, more efficient version: http://ideone.com/B8p7m0 http://ideone.com/B8p7m0 Edit: A better way to write the inner loop: http://ideone.com/wEfNyh http://ideone.com/wEfNyh Edit: When the values are initialized to 3, 4, 5 instead of 0, 0, 0, the program can be simplified to: http://ideone.com/oyNk1O http://ideone.com/oyNk1O
djeps 13y ago
I'm learning C/C++, tried to compile (http://ideone.com/T1xVLz http://ideone.com/T1xVLz) your code in ubuntu, with gcc-4.8, and an error about copy_n is not declared in this scope was raised. error: ‘copy_n’ was not declared in this scope what is the problem? Is it something to do with gcc-4.8 and shared libs? Thanks

39 points by jzwinck 13y ago

lelf 13y ago

This is different. They are combining streams in the original article. (‘Start with the stream of integers from 1 to infinity <…>’). Your code is take 10 mutable_spaghetti_function

dkhenry 13y ago
And as a trade off you get a much cleaner and more performant solution to the same contrived problem. This is where Haskell and functional coders tend to break down. Yes its mutable, but by violating that one rule you gain so much in terms of readability and performance.
- 5hoom 13y ago
  That's one thing I've noticed with my C++ code lately is that I'm writing const absolutely everywhere. Having mutability where you need it is awesome but it is interesting to see languages like Rust where immutability is the default.
  - jzwinck 13y ago
    I have done a bit of this too. The main downside in C++ is that you end up writing a few more ternary operators than you otherwise may have. But it is nice to be able to look at the first assignment of a variable and know it is the only one.
    - 5hoom 13y ago
      Yeah it kind of feels dirty having all these mutable variables around after doing any functional programming at all. I've found using const a lot also goes hand-in-hand with raii. If a member of a class is const it must be initialized in the constructor, and it just seems to make me code a bit more "hygienically".
- cgh 13y ago
  You are right about more performant, but how is it cleaner and more readable than this? pyth x = [(a,b,c) | a<-[1..x], b<-[1..x], c<-[1..x], (a^2)+(b^2) == (c^2)]
  - dkhenry 13y ago
    Thats not c++ code. My claim is that if you try to stay pure using C++ you end up with very very ugly code that preforms pretty poorly.
jzwinck 13y ago
Indeed. This is part of why I included "idiomatic" in the title here. Someone smarter than me already wrote a bit prettier iterator increment function, and using that is easy once you have the interface decided. And in C++, iterators abound, and can be used as infinite sequence generators with no difference to how they are normally used and understood. The code may be spaghetti, but I mostly just lifted it from the referenced article and solved the problems the original author brought up, namely the separation of concerns. The C++ solution to this problem will never be as beautiful as the Haskell one, but I wanted to show it doesn't have to be alienating for people who program C++ daily. C++ iterators are powerful, and can be used for a lot more than stepping through a container. We write too few of them.

zwegner 13y ago

All those if statements inside loops... would be a lot cleaner (and faster!) to just use a single goto statement: goto cont; for (; ; ++z) for (; x <= z; ++x) for (; y <= z; ++y) { if (x*x + y*y == z*z) return *this; cont: }

jzwinck 13y ago
I totally agree--thank you for bringing this up. I'm not sure it would be faster, but it is an interesting case for goto. I saw another proposal referencing the original article which used a trio of functions in a nice way to achieve something similar without the goto (and without the ifs). My main point was to illustrate the use of custom iterators.
- zwegner 13y ago
  Consider me nerd-sniped. I typed the last post on my phone, but just had to bust out the laptop to check. Noticed a couple bugs I had: the for-loop initializers need to be set, and there needs to be an empty statement after the cont: label. The goto version only has one unconditional branch outside of a loop, rather than three conditional branches inside loops. Anyways, the speed difference shouldn't be too big, as the branches are pretty predictable (pretty much always not taken). Quick benchmark of the original and mine, up to the first 3000 triples: $ c++ -O3 pyth1.cpp && time ./a.out | md5 33aa33d6cad59951489757e06aeb5a15 real 0m5.492s user 0m5.484s sys 0m0.007s $ c++ -O3 pyth2.cpp && time ./a.out | md5 33aa33d6cad59951489757e06aeb5a15 real 0m4.248s user 0m4.238s sys 0m0.011s
5hoom 13y ago
I'm always looking for a legitimate excuse to use a goto in my C++ code because I'm perverse. It's very rare to find one but this looks like it might be okay.
Pxtl 13y ago
All the crazy crap they added to C/C++, how was named loops and corresponding named break/continue not one of them?

pfultz2 13y ago

This can already be done using Linq in C++, which is range-based rather than iterator based: auto q = LINQ( from(z, boost::irange(1, std::numerical_limits<int>::max())) from(x, boost::irange(1, z)) from(y, boost::irange(1, x)) where(x*x + y*y == z*z) select(boost::fusion::make_vector(x, y, z)) ); for(auto&& x:q | linq::take(10)) std::cout << x << std::endl; Hopefully, once we get ranges in the C++ standard library, we can add list comprehension to the language, perhaps something like this: auto q = [ for (z, std::irange(1, std::numerical_limits<int>::max())) for (x, std::irange(1, z)) for (y, std::irange(1, x)) if (x*x + y*y == z*z) boost::fusion::make_vector(x, y, z) ]; for(auto&& x:q | std::take(10)) std::cout << x << std::endl;

deleted 13y ago
[deleted]

detrino 13y ago

A cleaner, more efficient version: http://ideone.com/B8p7m0 http://ideone.com/B8p7m0 Edit: A better way to write the inner loop: http://ideone.com/wEfNyh http://ideone.com/wEfNyh Edit: When the values are initialized to 3, 4, 5 instead of 0, 0, 0, the program can be simplified to: http://ideone.com/oyNk1O http://ideone.com/oyNk1O

djeps 13y ago

I'm learning C/C++, tried to compile (http://ideone.com/T1xVLz http://ideone.com/T1xVLz) your code in ubuntu, with gcc-4.8, and an error about copy_n is not declared in this scope was raised. error: ‘copy_n’ was not declared in this scope what is the problem? Is it something to do with gcc-4.8 and shared libs? Thanks