6 ms·

Manipulating C++ Containers Functionally

wonderzombie 14y ago
I was a little bit afraid to read this one. I've glanced at some of the functional patterns in the STL — function objects, ugh — and come away shaking my head. But despite my problems with C++ and/or the STL, I really appreciated this piece. The author seems to know his stuff pretty well, as there are references to Haskell, monoids, laziness, as well as a brief discussion of performance. It's probably too much to hope that this will win terribly many converts, but hey, what do I know?
- ahelwer 14y ago
  What's wrong with function objects? They're essentially functions with partial application.
Aardwolf 14y ago
I do agree that C++'s STL is sometimes too verbose. It's important to be generic, but it'd have been great if the most common conveniences were added as well to make it pleasant to use. E.g.: erase remove idiom, count but no contains, specifying begin() and end() even when you mean the whole container, ... Anything where you need to type the variable name of your container more than once to do one operation on it. Not just the containers and stl algorithms have that annoyance, but also the string stream operators to convert numbers to strings, this is way too verbose imho. At least the new initializer lists make some things way more compact and convenient now :)
- zainny 14y ago
  Fortunately with C++11 we no longer have to do the stringstream dance thanks to built-in stoi/stol string member functions: http://en.cppreference.com/w/cpp/string/basic_string/stol http://en.cppreference.com/w/cpp/string/basic_string/stol
  - splinterofchaos 14y ago
    Technically, those are free functions defined on strings, not members functions of the class string. But also: std::to_string http://en.cppreference.com/w/cpp/string/basic_string/to_string http://en.cppreference.com/w/cpp/string/basic_string/to_stri...
- akaus 14y ago
  There is STO library: http://github.com/lvv/sto http://github.com/lvv/sto > E.g.: erase remove idiom remove sub-string: string("abcd") - "cd" > specifying begin() and end() unary '+', '-' overloaded to return to begin()/end() > when you mean the whole container, ... Euler example in just one expression (with boost lambda): range(1000) | (!(_1%3) || !(_1%3)) | add
alexchamberlain 14y ago
I've recently discovered the delights of <algorithm>... now if I could just figure out how to bind member functions in my build environment (Solaris) I'd be a very happy man.
- splinterofchaos 14y ago
  You want either mem_fn (C++11) or mem_fun. http://en.cppreference.com/w/cpp/utility/functional http://en.cppreference.com/w/cpp/utility/functional
bcoates 14y ago
I think going this way is going to turn out painful. The sort of immutable container logic that people associate with FP is against the nature of C++ and you'll be constantly bumping into other people's code, and parts of the library, that don't like it. C++ style prefers for_each(xs.begin(), xs.end(), f); to xs = std::transform(xs,f); Because the first does not copy the container and its elements, which in C++ is a meaningful operation which may not be allowed for xs's elements, or may be remarkably expensive. I thought the annoying verbosity when using the whole container with <algorithm> was fixed in C++11 like it was for for loops, but I can't find documentation to that effect. Boost's range algorithms library is still useful here: http://www.boost.org/doc/libs/1_52_0/libs/range/doc/html/index.html http://www.boost.org/doc/libs/1_52_0/libs/range/doc/html/ind...
- splinterofchaos 14y ago
  > The sort of immutable container logic that people associate with FP is against the nature of C++... My argument is that C++, a multi-paradigm language, benefits from not being bound to purity and that being able to mix imperative and functional code is a good thing. We aren't stuck in pure-land so we can insert IO where it needs to be, not where it propagates, but neither do we need to be stuck in state-land. Functional programming is not against the "nature" of the language, it gives us the freedom to choose. > Because the first does not copy the container and its elements... This is a quality of implementation detail. It would have been detrimental to the point of the article to waste time showing optimizations such as "if F is a function X to X, use the in-place version". But I assure you, my optimization testing has shown there is little difference between the code generated by this and vanilla <algorithm>. In fact, it is at times better. https://github.com/splinterofchaos/Pure/blob/master/samples/efficiency-fold-map.cpp https://github.com/splinterofchaos/Pure/blob/master/samples/...
  - eswangren 14y ago
    Yeah, but those "implementation details" are often relevant. I want to know if I am creating a bunch of extraneous copies when iterating through a container. It may not always matter, but sometimes it does, and performance matters more than functional purity.

I was a little bit afraid to read this one. I've glanced at some of the functional patterns in the STL — function objects, ugh — and come away shaking my head. But despite my problems with C++ and/or the STL, I really appreciated this piece. The author seems to know his stuff pretty well, as there are references to Haskell, monoids, laziness, as well as a brief discussion of performance. It's probably too much to hope that this will win terribly many converts, but hey, what do I know?

ahelwer 14y ago
What's wrong with function objects? They're essentially functions with partial application.

Aardwolf 14y ago

I do agree that C++'s STL is sometimes too verbose. It's important to be generic, but it'd have been great if the most common conveniences were added as well to make it pleasant to use. E.g.: erase remove idiom, count but no contains, specifying begin() and end() even when you mean the whole container, ... Anything where you need to type the variable name of your container more than once to do one operation on it. Not just the containers and stl algorithms have that annoyance, but also the string stream operators to convert numbers to strings, this is way too verbose imho. At least the new initializer lists make some things way more compact and convenient now :)

zainny 14y ago
Fortunately with C++11 we no longer have to do the stringstream dance thanks to built-in stoi/stol string member functions: http://en.cppreference.com/w/cpp/string/basic_string/stol http://en.cppreference.com/w/cpp/string/basic_string/stol
- splinterofchaos 14y ago
  Technically, those are free functions defined on strings, not members functions of the class string. But also: std::to_string http://en.cppreference.com/w/cpp/string/basic_string/to_string http://en.cppreference.com/w/cpp/string/basic_string/to_stri...
akaus 14y ago
There is STO library: http://github.com/lvv/sto http://github.com/lvv/sto > E.g.: erase remove idiom remove sub-string: string("abcd") - "cd" > specifying begin() and end() unary '+', '-' overloaded to return to begin()/end() > when you mean the whole container, ... Euler example in just one expression (with boost lambda): range(1000) | (!(_1%3) || !(_1%3)) | add

alexchamberlain 14y ago

I've recently discovered the delights of <algorithm>... now if I could just figure out how to bind member functions in my build environment (Solaris) I'd be a very happy man.

splinterofchaos 14y ago
You want either mem_fn (C++11) or mem_fun. http://en.cppreference.com/w/cpp/utility/functional http://en.cppreference.com/w/cpp/utility/functional

bcoates 14y ago

I think going this way is going to turn out painful. The sort of immutable container logic that people associate with FP is against the nature of C++ and you'll be constantly bumping into other people's code, and parts of the library, that don't like it. C++ style prefers for_each(xs.begin(), xs.end(), f); to xs = std::transform(xs,f); Because the first does not copy the container and its elements, which in C++ is a meaningful operation which may not be allowed for xs's elements, or may be remarkably expensive. I thought the annoying verbosity when using the whole container with <algorithm> was fixed in C++11 like it was for for loops, but I can't find documentation to that effect. Boost's range algorithms library is still useful here: http://www.boost.org/doc/libs/1_52_0/libs/range/doc/html/index.html http://www.boost.org/doc/libs/1_52_0/libs/range/doc/html/ind...

splinterofchaos 14y ago
> The sort of immutable container logic that people associate with FP is against the nature of C++... My argument is that C++, a multi-paradigm language, benefits from not being bound to purity and that being able to mix imperative and functional code is a good thing. We aren't stuck in pure-land so we can insert IO where it needs to be, not where it propagates, but neither do we need to be stuck in state-land. Functional programming is not against the "nature" of the language, it gives us the freedom to choose. > Because the first does not copy the container and its elements... This is a quality of implementation detail. It would have been detrimental to the point of the article to waste time showing optimizations such as "if F is a function X to X, use the in-place version". But I assure you, my optimization testing has shown there is little difference between the code generated by this and vanilla <algorithm>. In fact, it is at times better. https://github.com/splinterofchaos/Pure/blob/master/samples/efficiency-fold-map.cpp https://github.com/splinterofchaos/Pure/blob/master/samples/...
- eswangren 14y ago
  Yeah, but those "implementation details" are often relevant. I want to know if I am creating a bunch of extraneous copies when iterating through a container. It may not always matter, but sometimes it does, and performance matters more than functional purity.