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.
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.):
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 ?
"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.
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.
I write performance critical software for a living (industrial image recognition) and I often try to squeeze the last few percent out of an algorithm. But even in my case the by far largest part of code I write is not performance relevant at all. And there I prefer terseness and readability over performance. Yes, there can be some cases where I have to switch to a more efficient version later, because profiling shows a bottleneck where I did not expect one to be. But in my experience this has never been too big of a problem to sacrifice readability from the beginning in all places.
I wasn't discussing readability, but rather performance. The two are not mutually exclusive. Nor was I picking on the "last few percent" of performance--the shortcoming in speed of the "I in team" example is likely an order of magnitude or more. And it isn't fixable without modifying the API.
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."
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.
I hear a lot of people complain about higher levels of abstraction in languages like C and C++, because they take away control or don't allow them to squeeze every last drop of performance out of their programs.
I also see a lot of software in the wild that was programmed in C and C++ and runs very fast... but is buggy as hell or has pretty nasty security bugs.
The fact is that, regardless how good you think you are, most likely you're not one of the few people who can write fast, bug-free[0] software in C and C++. I certainly am not despite having written quite a bit of C and C++ in the over the years. The amount of high-impact bugs (especially security bugs, eg Heartbleed)
[0] Where I really mean: no severe bugs (data corruption, data loss, security flaws)
What you say is somewhat true most of the time when you are writing an application. However, when I am writing a library I have far less control over situations where functions in that library will get called. So it makes sense to make the library lean and lacking obvious bloats, or at least make efficient code paths possible without forcing the application programmer to indulge in excessive verbosity. This makes the library more broadly usable.
As an application developer its a big pain to realize that the library that you have built your application around now needs to be incised out for performance reasons. In theory, if you design your interface well one can switch out libraries, but it is rarely as clean as what theory claims. Interfaces set, if not in stone, at least in in loose concrete, the data-structures that are convenient to use.
EDIT: I hasten to add that I am not complaining about the library, far from it.
> it makes sense to make the library lean and lacking obvious bloats, or at least make efficient code paths possible without forcing the application programmer to indulge in excessive verbosity.
Does not apply to these people:
> 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.
who, by definition, are not experienced enough to write code that is sufficiently lean and lacking obvious bloat, or at least make efficient code paths possible. If they were, then they won't have a problem with the pretty package either.
Oh, I know - it was from the post which you replied to.
I only wanted to point out that in the context of the comment you replied to, I didn't feel that those were the people who should be worrying about optimised code.
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.
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.
Streaming fusion exists, and can easily be implemented in C++, that's what authors of this library should have done. C++ ranges library (proposition for C++17) will make this kind of thing possible without any overhead. Realistically, STL interface for sequences is pretty bad and barely composable.
This is not a problem with "functional style", it's a problem with library design.
writing
map (+2) (map (+1) (map (+3) xs))
will be just a single pass over a list in Haskell, with 3 function applications (maybe 1 if that is optimized to (+6)).
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.
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
That's a shame there's nothing similar in the C++ standard library.
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.
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_fr...
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.
See https://github.com/facebook/folly/blob/master/folly/gen/test... for an example.