6 ms·

FunctionalPlus – helps you write concise and readable C++ code

57 points by Dobiasd 11y ago

Dobiasd 11y ago
While working on my last projects I accumulated a collection of pure functions I needed now and then. So I thought, why not write a short pitch as a README and make it public? So here it is. It would be very nice of you if you could tell me what you think, so I can learn and improve.
- Ace17 11y ago
  Although an implementation based on streaming combinators (=no intermediate allocations) clearly is faster, the interface you provided definitely corresponds to the way I want to program. You might want to have a look to std.algorithm from Phobos (the D programming language standard library) ; it's full of such utilities : http://dlang.org/phobos/std_algorithm.html http://dlang.org/phobos/std_algorithm.html That's a shame there's nothing similar in the C++ standard library.
- frozenport 11y ago
  I generally use python when manipulating lists, and C++ for floating point oriented tasks.
  - Dobiasd 11y ago
    What do you do if your application needs to do both?
    - frozenport 11y ago
      Thats a great question! In one case I used a python wrapper around a C++ core, but when it came time to re-write it we switched to pure python and have so far hit our performance benchmarks - mostly because libraries like OpenCV or PyCuda are now able to efficiently wrap our critical paths.
  - Ace17 11y ago
    The OP's work shows it clearly is possible to manipulate lists in C++, in a simple and concise way.
- vitd 11y ago
  I'll just say that it looks very interesting, and it's the type of thing that might help me to better learn functional programming. I jumped in with Haskell a year or two ago, and while it was interesting, learning it has been a pain because it's so different from imperative programming. Something like this where I can dip a toe in a little at a time in a language I already understand looks appealing. I'm not concerned about efficiency of code in this case, just efficiency of learning the concepts.
  - Dobiasd 11y ago
    Great to hear that. Good luck on your journey to functional programming. I also started with Haskell and had problems with it. Then I found Elm, and that was like of a gateway drug for me. Here is my story in case you are interested: https://github.com/Dobiasd/articles/blob/master/switching_from_imperative_to_functional_programming_with_games_in_Elm.md https://github.com/Dobiasd/articles/blob/master/switching_fr...
jzwinck 11y ago
One of the main reasons to use C++ today is the potential for high performance. One of the examples given is a great demonstration of what not to do: allocate a new container on the heap, scan it once, and delete it. I'm talking about the "I in team" example, which if you coded it by hand would almost certainly use a better algorithm. It's hard enough teaching people to avoid inefficiency when it's right there in front of them, and harder still when you encapsulate inefficiency in a pretty package. This is why some "obvious" functions don't exist in the STL.
- userbinator 11y ago
  Your comment reminds me that, from the other direction, those who make arguments for the performance of functional languages like Haskell often give example code that doesn't look very "functional" at all. One sentence that comes to mind is "If you write C++ like you write Java, you are unlikely to see any benefit."
- Ace17 11y ago
  Actually, teaching people how to avoid inefficiencies might transform "slow code" to "slow and unmaintainable code". It's more strategic to teach people to write readable code (exactly like the OP does), and then ... to teach them how to use a profiler.
  - jzwinck 11y ago
    How is a profiler going to help if your code is riddled with inefficient structures? The "I in team" example can be made more efficient if SplitWords returns an iterator, but SplitWords itself won't be possible to change once it is ingrained in a codebase (because e.g. some call sites will come to depend on it returning a list). I love profilers as much as the next person, but if you build a system from inefficient building blocks, you may eventually need to build it again. But in a professional setting you are likely to be told not to do build it a second time, or you will be gone before that time comes, leaving someone else to clean up your moribund codebase of a thousand inefficiencies.
    - 11y ago
ajtulloch 11y ago
I would recommend instead Facebook's folly::gen library, which provides these functional combinators in a high-performance fashion, by expressing them as streaming combinators. You get all the map/filter/take/drop/reduce primitives, but in a much cleaner way. See https://github.com/facebook/folly/blob/master/folly/gen/test/BaseTest.cpp https://github.com/facebook/folly/blob/master/folly/gen/test... for an example.
- arximboldi 11y ago
  Or Atria's transducers library (a-la Clojure), which can be applied to collections but also to pushy things (e.g. boost.signals, rx.observables, etc.): Code: https://github.com/Ableton/atria/tree/master/src/atria/xform/transducer https://github.com/Ableton/atria/tree/master/src/atria/xform... CppCon 2015 session: http://sinusoid.es/talks/transducers-cppcon15/ http://sinusoid.es/talks/transducers-cppcon15/ https://www.youtube.com/watch?v=vohGJjGxtJQ https://www.youtube.com/watch?v=vohGJjGxtJQ
- echaozh 11y ago
  The coming standard: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n412...
- moonchrome 11y ago
  I see all these nice C++ libraries like Facebook folly and then I see that they bring in boost and megabytes of include files for trivial stuff bringing in stuff I absolutely don't need (or ever will, in fact most of it is for dealing with legacy compilers and OSes I don't care about). Maybe it's just me but I don't like half an hour compile times. Am I missing something or has everyone else using it just accepted the compile times ?
  - jzwinck 11y ago
    "Bringing in Boost" doesn't cost you much at all in terms of compile time. Using some of the advanced template meta-programming stuff in it may, but basic things like the legacy compiler and OS support you mention are largely using the C preprocessor and take very little time. In other words, give it a try--I'm sure you won't have half an hour compile times just by using Folly. If you want to compile C++ (or C) really fast, look at icecc: https://github.com/icecc/icecream https://github.com/icecc/icecream
makecheck 11y ago
The examples are clearly achieving the goal of "concise". I would counter with a different style though, because I try to imagine how the code would change over time and how it would fare when given constraints on memory and runtime. Compare: for (int x : numbers) { if (1 == (x % 2)) { odds.push_back(x); } } auto odds = KeepIf(IsOdd, numbers); To me, the first case is preferable. The 2nd case uses custom functions that may not be familiar to the maintainer, and semantics are clearly hidden (e.g. does KeepIf() modify the list, return a copy, or return some kind of intelligent generator object that still depends on the lifetime of "numbers"?). Suppose I discover that my application starts crashing with the odd number 15 and I have to work around that case very quickly. The loop version above is trivial to modify, whereas I have no idea how the 2nd version would be modified to filter out one value! And if I want to do several things with the numbers while they're being found (e.g. print them out), the loop is easy to change but the 2nd version basically has to be replaced entirely (and replacing even a concise expression is risky due to the issues above, e.g. unclear semantics). Now compare approaches for another case: if (FindWord("I", team)) ... if (Contains("I", SplitWords(team))) ... This shows a general problem with a "functional style" at times: it's placing constraints on the implementation that don't need to be there. To me, the first style is preferable because FindWord() could easily walk a raw string and stop as soon as it finds the target word, with a chance for better-than-N average complexity. The second case would mandate: copying strings, visiting all characters in the string every time, and revisiting at least some of the characters in the form of words. Finally, I think that the C++ standard algorithms, lambdas, and compact-"for" do allow a lot of these tricks to be avoided. Consider algorithms like std::all_of() for instance, which can be combined with lambdas to produce the same results as examples like "AllBy(And(..." but without the downsides I mention at the beginning of my comment.
- Dobiasd 11y ago
  I really like your remark about the performance of if (Contains("I", SplitWords(team))) so I added it to the README. If you don't want the 15 in the odds, just to this: auto goodOdds = without(15, keep_if(is_odd, numbers)); The fact, that `keep_if` does return a copy can easily obtained by looking at the function signature or the type of `odds`. Both things should not be complicated with a modern IDE. I agree with you in general. The library is not made for performance-critical stuff. But the "raw loops etc. are easier to understand by outsiders" seems like an argument agains using any libraries at all.

57 points by Dobiasd 11y ago

While working on my last projects I accumulated a collection of pure functions I needed now and then. So I thought, why not write a short pitch as a README and make it public? So here it is. It would be very nice of you if you could tell me what you think, so I can learn and improve.

Ace17 11y ago
Although an implementation based on streaming combinators (=no intermediate allocations) clearly is faster, the interface you provided definitely corresponds to the way I want to program. You might want to have a look to std.algorithm from Phobos (the D programming language standard library) ; it's full of such utilities : http://dlang.org/phobos/std_algorithm.html http://dlang.org/phobos/std_algorithm.html That's a shame there's nothing similar in the C++ standard library.
frozenport 11y ago
I generally use python when manipulating lists, and C++ for floating point oriented tasks.
- Dobiasd 11y ago
  What do you do if your application needs to do both?
  - frozenport 11y ago
    Thats a great question! In one case I used a python wrapper around a C++ core, but when it came time to re-write it we switched to pure python and have so far hit our performance benchmarks - mostly because libraries like OpenCV or PyCuda are now able to efficiently wrap our critical paths.
- Ace17 11y ago
  The OP's work shows it clearly is possible to manipulate lists in C++, in a simple and concise way.
vitd 11y ago
I'll just say that it looks very interesting, and it's the type of thing that might help me to better learn functional programming. I jumped in with Haskell a year or two ago, and while it was interesting, learning it has been a pain because it's so different from imperative programming. Something like this where I can dip a toe in a little at a time in a language I already understand looks appealing. I'm not concerned about efficiency of code in this case, just efficiency of learning the concepts.
- Dobiasd 11y ago
  Great to hear that. Good luck on your journey to functional programming. I also started with Haskell and had problems with it. Then I found Elm, and that was like of a gateway drug for me. Here is my story in case you are interested: https://github.com/Dobiasd/articles/blob/master/switching_from_imperative_to_functional_programming_with_games_in_Elm.md https://github.com/Dobiasd/articles/blob/master/switching_fr...

jzwinck 11y ago

One of the main reasons to use C++ today is the potential for high performance. One of the examples given is a great demonstration of what not to do: allocate a new container on the heap, scan it once, and delete it. I'm talking about the "I in team" example, which if you coded it by hand would almost certainly use a better algorithm. It's hard enough teaching people to avoid inefficiency when it's right there in front of them, and harder still when you encapsulate inefficiency in a pretty package. This is why some "obvious" functions don't exist in the STL.

userbinator 11y ago
Your comment reminds me that, from the other direction, those who make arguments for the performance of functional languages like Haskell often give example code that doesn't look very "functional" at all. One sentence that comes to mind is "If you write C++ like you write Java, you are unlikely to see any benefit."
Ace17 11y ago
Actually, teaching people how to avoid inefficiencies might transform "slow code" to "slow and unmaintainable code". It's more strategic to teach people to write readable code (exactly like the OP does), and then ... to teach them how to use a profiler.
- jzwinck 11y ago
  How is a profiler going to help if your code is riddled with inefficient structures? The "I in team" example can be made more efficient if SplitWords returns an iterator, but SplitWords itself won't be possible to change once it is ingrained in a codebase (because e.g. some call sites will come to depend on it returning a list). I love profilers as much as the next person, but if you build a system from inefficient building blocks, you may eventually need to build it again. But in a professional setting you are likely to be told not to do build it a second time, or you will be gone before that time comes, leaving someone else to clean up your moribund codebase of a thousand inefficiencies.
  - 11y ago

ajtulloch 11y ago

I would recommend instead Facebook's folly::gen library, which provides these functional combinators in a high-performance fashion, by expressing them as streaming combinators. You get all the map/filter/take/drop/reduce primitives, but in a much cleaner way. See https://github.com/facebook/folly/blob/master/folly/gen/test/BaseTest.cpp https://github.com/facebook/folly/blob/master/folly/gen/test... for an example.

arximboldi 11y ago
Or Atria's transducers library (a-la Clojure), which can be applied to collections but also to pushy things (e.g. boost.signals, rx.observables, etc.): Code: https://github.com/Ableton/atria/tree/master/src/atria/xform/transducer https://github.com/Ableton/atria/tree/master/src/atria/xform... CppCon 2015 session: http://sinusoid.es/talks/transducers-cppcon15/ http://sinusoid.es/talks/transducers-cppcon15/ https://www.youtube.com/watch?v=vohGJjGxtJQ https://www.youtube.com/watch?v=vohGJjGxtJQ
echaozh 11y ago
The coming standard: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n412...
moonchrome 11y ago
I see all these nice C++ libraries like Facebook folly and then I see that they bring in boost and megabytes of include files for trivial stuff bringing in stuff I absolutely don't need (or ever will, in fact most of it is for dealing with legacy compilers and OSes I don't care about). Maybe it's just me but I don't like half an hour compile times. Am I missing something or has everyone else using it just accepted the compile times ?
- jzwinck 11y ago
  "Bringing in Boost" doesn't cost you much at all in terms of compile time. Using some of the advanced template meta-programming stuff in it may, but basic things like the legacy compiler and OS support you mention are largely using the C preprocessor and take very little time. In other words, give it a try--I'm sure you won't have half an hour compile times just by using Folly. If you want to compile C++ (or C) really fast, look at icecc: https://github.com/icecc/icecream https://github.com/icecc/icecream

makecheck 11y ago

The examples are clearly achieving the goal of "concise". I would counter with a different style though, because I try to imagine how the code would change over time and how it would fare when given constraints on memory and runtime. Compare: for (int x : numbers) { if (1 == (x % 2)) { odds.push_back(x); } } auto odds = KeepIf(IsOdd, numbers); To me, the first case is preferable. The 2nd case uses custom functions that may not be familiar to the maintainer, and semantics are clearly hidden (e.g. does KeepIf() modify the list, return a copy, or return some kind of intelligent generator object that still depends on the lifetime of "numbers"?). Suppose I discover that my application starts crashing with the odd number 15 and I have to work around that case very quickly. The loop version above is trivial to modify, whereas I have no idea how the 2nd version would be modified to filter out one value! And if I want to do several things with the numbers while they're being found (e.g. print them out), the loop is easy to change but the 2nd version basically has to be replaced entirely (and replacing even a concise expression is risky due to the issues above, e.g. unclear semantics). Now compare approaches for another case: if (FindWord("I", team)) ... if (Contains("I", SplitWords(team))) ... This shows a general problem with a "functional style" at times: it's placing constraints on the implementation that don't need to be there. To me, the first style is preferable because FindWord() could easily walk a raw string and stop as soon as it finds the target word, with a chance for better-than-N average complexity. The second case would mandate: copying strings, visiting all characters in the string every time, and revisiting at least some of the characters in the form of words. Finally, I think that the C++ standard algorithms, lambdas, and compact-"for" do allow a lot of these tricks to be avoided. Consider algorithms like std::all_of() for instance, which can be combined with lambdas to produce the same results as examples like "AllBy(And(..." but without the downsides I mention at the beginning of my comment.

Dobiasd 11y ago
I really like your remark about the performance of if (Contains("I", SplitWords(team))) so I added it to the README. If you don't want the 15 in the odds, just to this: auto goodOdds = without(15, keep_if(is_odd, numbers)); The fact, that `keep_if` does return a copy can easily obtained by looking at the function signature or the type of `odds`. Both things should not be complicated with a modern IDE. I agree with you in general. The library is not made for performance-critical stuff. But the "raw loops etc. are easier to understand by outsiders" seems like an argument agains using any libraries at all.