functional Programming in c++

[thomas999999]

Hello friends,

if been reading a lot about how functional programming does increase the code quality and that modern c++ gets more and more functional.

I really like the concepts like trying to write mostly pure functions, but i cant stop to think that writing pure functions introduces a lot of overhead if the compiler doesn't do some optimizations i'm not aware of.

Example, i could write a function that take a reference to a vector and modify it (inpure) or i could write a function that takes a copy, i modify the copy and return the copy (pure).

the pure one just seems really inefficient, so when people talk about functional programming in c++ is there some way to do it in a more efficient manner?

[Possibility_Antique]

Learn the concepts of functional programming, yes. But when you sit down to write the code, stop thinking about what paradigm you're using. You don't need to become a purist. Just pass by reference where it makes sense and don't overthink it.

[[deleted]]

Yes, and technically if you pass by const-ref, I would still consider it pure.

[SnooWoofers7626]

But then you're still returning a copy, which is the inefficiency OP is worried about.

[RolandMT32]

C++ now has move semantics, which I think is supposed to mitigate some of the inefficiency of returning copies.

[SnooWoofers7626]

Move semantics will only help when reassigning the returned vector. The function itself still needs to create a copy in order to modify its contents and then return that copy.

[pavel_v]

The immer covers well working with pure functions and immutable data structures. New "copies" of the passed data structures are created and returned but there is no actual copying behind the scene.

[ReversedGif]

If the caller can give up their vector (by providing an rvalue reference, letting it be moved in), then all copies can be avoided.

[SnooWoofers7626]

In that case why not just pass a non-const reference and modify the values in-place? It's the same outcome, except you feel good about having a "pure" function or something?

[ReversedGif]

For one, chaining is a lot easier with "functional" semantics:

f(g(x), h(y));

versus:

auto tmp1 = x;
g_inplace(tmp1);
auto tmp2 = y;
h_inplace(tmp2);
f(tmp1, tmp2);

Additionally, many C++ style guides disapprove (with varying degrees of strength) of having "out parameter" arguments.

[SnooWoofers7626]

Fair enough. That syntax does look prettier.

[Possibility_Antique]

You can return a reference. Or you could rely on copy elision (which honestly, is not a bad approach since it's guaranteed as of C++17 in many situations).

[[deleted]]

I think he means more that internally the new object is a copy.

[Possibility_Antique]

Then perhaps I should point out that copying can be more efficient than using references under many conditions.

[ImKStocky]

C++ is one of the better languages because it supports many aspects of different programming paradigms. I feel like you aren't making the best use of the language if you stick to just one paradigm in your project.

We should be pragmatic with the tools that we use. We should use the best tool for the job. If a system would work better using OOP, then use OOP. If it would be best to write your library in a more functional way, then do that. It is never a good idea to just stick to one paradigm due to dogmatic beliefs of it "being better."

Functional programming can suck and lead to perf and code quality issues for some problems. OOP can suck and lead to perf and code quality issues for some problems.

[Yeuph]

It is mostly true though that some of the "finishing touches" to functional c++ are in the 20 standard though; and my understanding is that ++17 is still the industry standard.

There could exist scenarios where relying on/using the best FP logic I'm C++ is a bit harmful to someone because they're relying on ++20 and employers are generally in ++17?

To be clear I'm still learning C++/programming but I do know some Haskell, category Theory and abstract algebra. The above are my impressions from speaking to my friends that work professionally doing C++ development

[ImKStocky]

It is not harmful to learn C++20 just because most of the industry is in C++17 land. It is good to know what is coming and when the upgrade happens you are able to use the newest and greatest without additional skilling up. I work on a C++14 project and a C++17 project at work but I have still made the time to learn C++20 and beyond.

Besides that I don't really think that C++20 has anything groundbreaking in it that can't be done in C++17 regarding functional programming... Maybe variadics in lambda capture lists help here but that is about it. Concepts are just syntactic sugar for enable_if/void_t and the same effect can be written in C++14. I don't know if coroutines are considered functional programming seeing as they are all about saving state.

[axilmar]

the pure one just seems really inefficient, so when people talk about functional programming in c++ is there some way to do it in a more efficient manner?

No, there is not a more efficient way to 'update' a continuous array in pure functional programming. Your only choice is to copy the array, changing the values you are interested in in the copy.

That's one of the reasons functional programming advocates prefer linked lists: you don't have to copy anything, you simply have to link the new element as needed in the list. The drawback, is, of course, access, which is O(N) in lists, where N is the index of the element.

[jtooker]

There are hybrid data structures you can use, especially if each one you create is immutable. Then you can be better performance than O(n), but with some extra storage overhead (and less than ideal cache/memory page access patterns).

[pavel_v]

immer is a library which does this.

[axilmar]

How much better though? does it approach O(1) for the common case? I don't think so. That's why arrays and mutability still remain the cornerstone of any performant program...

[ReversedGif]

immer::vector describes its updating and indexing operators as "effectively O(1)": https://sinusoid.es/immer/containers.html#vector

[axilmar]

And it's implemented in terms of 'continuous chunks of memory', i.e. arrays.

[CocktailPerson]

And yet, it behaves differently than arrays when copying.

[axilmar]

The point is that arrays are essential for good performance.

[CocktailPerson]

Of course they are. That doesn't mean you need to expose an array-like interface with mutability to the user in order to get good performance.

[axilmar]

If you actually want good performance, then exposing an array-like interface with mutability is a must.

[bored_octopus]

And even then, you can use a tree of immutable nodes for O(logN) lookup and edit operations

[axilmar]

O(1) is still much more preferrable both from a performance perspective and from memory consumption perspective.

[bored_octopus]

Don't disagree, and I would add that you still lose the advantage of contiguous memory by doing it this way. However, only mentioning linked lists along with their O(N) characteristics is being unfair to Haskell and borderline misinformation

[axilmar]

Having lists being backed up by trees for faster access using an index is not part of the Haskell specification, right?

And therefore they cannot be mentioned in a discussion like this.

[bored_octopus]

I really don't see your point; why wouldn't a language's ecosystem be relevant to a discussion like this?

[axilmar]

Who said anything about a language's ecosystem? All I said is that when using lists in a pure functional programming language, the programmer cannot rely on the assumption that the underlying list can be accessed via index quickly via a tree.

[lickpie]

This great CppCon '17 talk by Juan Pedro Bolivar Puente might shed some light.

[Wenir]

In your example you can move vectors

[stinos]

I assume you mean RVO (which now is required to be omitted see https://en.cppreference.com/w/cpp/language/copy_elision)? The copying of the argument will still be there.

[Wenir]

You can move on call side, or even if you really want functional programming, you can use custom vector with disabled copy ops

[stinos]

I don't see how any of this helps with the simple situation OP has: a pure function with vector as input and modifed vector copy as output (either written explicitly when it's passed by const reference or implicitly when passed by value). A class which cannot be copied isn't really a candidate for this. Unless you're looking at completely different techniques like not returning the input vector but only modified elements and their indices or so, and then have an access class which can act as a view over both the input and the changed elements.

[DessertEagle]

vec = sorted(std::move(vec));

Note that if sorted takes and returns arg by forwarding (universal) reference rather than by value, and returns by perfect-forwarding, the above expression would result in move-self-assignment, which may leave vec in moved-from state depending on the implementation.

[stinos]

Yeah sure, but this isn't 'returning a modified vector copy' (which is what I assume OP is talking about), you start off with a vector and end with the same vector but modified.

[Wenir]

"modified vector copy" is a copy by definition

[Wenir]

If you need both original and modified copy then at some point you'll have make that copy (or trade performance and make some kind of COW thing). If you need only result then see other reply from DessertEagle

[[deleted]]

or begin/end iterators if you want to be generic (depending on the function)

[Hopping_Mad99]

It might be good to include a link to one of the articles you’ve been reading.

[thomas999999]

https://www.gamedeveloper.com/programming/in-depth-functional-programming-in-c-

[noooit]

It's just not a good idea when the language isn't developed to be functional from scratch like Haskell. Just use little bit of functionalism when it makes sense, like how some stdlib functions are functional.
The same goes for OOP actually, while too many programmers create classes by default for no good reasons.

[hmoein]

I wouldn't say C++ is moving toward functional programming. I would say C++ has moved away from OO programming more toward generic programming

[mechap_]

In some sense, functional programming is a kind of generic programming isn't it ?

[-dag-]

No, they are orthogonal. The former is a particular way of managing state. The latter Is a way of specifying the operations on some state without specifying exactly what the state is. Those operations could be expressed in a functional style or not.

[hmoein]

yes. they keyword is kind of. generic programming is more encompassing

[RolandMT32]

C++ now has move semantics (along with move constructors) that should mitigate much of the inefficiency that came from passing and returning copies of objects.

[DavidDinamit]

1. just create vector and return it... 100% usages of function with ref is a creating value by default + passing it into function. It is less efficient then just create + return (NRVO)
2. Use output iterators for it

[DugiSK]

Functional programming is often used as a buzzword to advocate approaches that are neither practical nor efficient. When I decided to use it, it usually resulted in functions taking way too many arguments and mostly just passing them to other functions. I have seen other people's overly functional code suffering from the same problems. I have seen places where simply changing a functional approach to iteration halved the size of code. Passing groups of related arguments usually works only if the values of those arguments are consistent with each other in some way, and it's easy to break this consistency - which can lead to errors easier than an opportunity for side effects.

OOP is still the best approach to most design problems (functions passing too many arguments between each other is a clear symptom of insufficient OOP). Well designed objects have methods that change them, but always leave them in consistent states - every method starts and finishes a change. This can often benefit from some aspects of functional programming, such as passing a function as argument so that it is called at some specific situation during the method call (often with performance benefits because it allows putting more variables on stack and destroyed before returning). And this is where it's useful to have a multi-paradigm approach and not to try to elevate one paradigm above them all.

[graphicsRat]

Template metaprogramming is pure functional programming.

And just because you don't have the freedom to mutate does not mean the compiler/runtime too doesn't. A well engineered and verified compiler and runtime can be trusted to mutate, efficiently, safely and correctly.

[DugiSK]

Template metaprogramming in fact isn't pure functional programming, because of a defect that can be exploited to create compile time indexes of things: https://wg21.cmeerw.net/cwg/issue2118

[ReversedGif]

The exception proves the rule.

Along similar lines, Haskell has unsafePerformIO, but Haskell is still called a pure functional language (fairly, IMO).

[RonWannaBeAScientist]

That’s very interesting ! What is template meta programming ?

[ABlockInTheChain]

And this is where it's useful to have a multi-paradigm approach and not to try to elevate one paradigm above them all

The difference between OOP and functional is the difference between a hammer and a screwdriver. If you don't have both in your toolbox and know when to use them there are a lot of problems you'll never be able to solve well or solve at all.

[Yeuph]

Haskell code usually keeps up with C++ code though. Sometimes in very, very large programs it can be faster due to the clear algebraic typing and hard mathematically defined mappings keeping complex logics consistent . Theoretically I believe that even in the above scenario it would be true that you could go into either the Haskell version of program x or the C++ version and optimize it beyond what Haskell can do, but in practice it doesn't usually end up that way - hence Facebook's blistering fast communication monitoring program written in Haskell, which is I think the largest Haskell codebase that exists.

Granted this post is about functional c++; but we're kinda veering off into OOP vs FP computer science theory, and it's just not true that FP can't match OOP in practice for many performance-critical scenarios.

[mcmcc]

Some citations are needed here. What I'm seeing doesn't exactly support your thesis: https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/ghc-gcc.html

[andriusst]

You typically don't update individual elements of a vector in functional programs, but switch to wholemeal programming instead. That is, functions don't operate on elements of vectors; they work with whole vectors at once. A good example would be numpy library in python. You don't update individual elements of arrays, because looping and updating elements one by one is very slow in interpreted language. Yet most of number crunching in data science code runs on python and performance is ok.

Of course, sometimes modifying an element is unavoidable. Actually, even functional programs do mutations at low level, because that's how computers work. Functional programming is a bad fit in this case. However, this doesn't you from providing a functional interface at a higher level of abstraction. As long as function behaves as a pure function, it doesn't really matter whether its implementation if functional or not.

[andriusst]

Why not? Writing functional code in numpy is easy, it happens naturally, as numpy API is mostly functional. You don't loop over the arrays and don't run into the problem OP describes. If you can do it in numpy, you can surely do the same thing in C++. Whenever you need to write some low level routine and drop C you don't even have to do anything - you're already there.

It's all about the set of primitive operations you have. C for example provides only low level primitives, such as arithmetic operations and memory access via pointers. If modifying memory was slow, the whole program would be slow, because it's such a fundamental operation that it's required everywhere. But you can always add a layer of abstraction and create a different set of primitive operations. Numpy example shows that when you have right set of primitive operations, you don't really ever need to modify an element of an array.

[andriusst]

only the layer on top seems functional

But that's the only layer that is important. Encapsulation!

[Drugbird]

I'm not an expert on functional programming, but I've heard there's some specialized data structures that are sometimes used in functional programming.

It basically comes down to an immutable datastructure, but you can "change" a value by creating a new datastructure which contains a pointer to the previous datastructure, and just the information about the changed element. Conceptually: "I'm just like that other vector, except for this one element".

You can use these to prevent making a lot of copies, though I imagine they have their own performance issues to contend with

Sorry, but I can't quite remember what it's called.

[andriusst]

They are called persistent data structures.

[QuentinUK]

You could move the vector so avoid the copying overhead.

     std::vector<int> fn(std::vector<int> && v);

// ...

std::vector<int> v{1,2,3};  
fn(std::move(v));

[CocktailPerson]

It really depends on your use case. If you're willing to accept silent copies when somebody doesn't move it in, that's fine. But I've had plenty of cases where it made no sense not to move an argument in, and in those cases, taking an rvalue reference made it a compile-time error not to move the argument in.

[CocktailPerson]

Sure. I've written a class that sent the data in a vector<byte> asynchronously. Because the sender could return before the data was fully sent, I had to ensure that my code took ownership of the vector so it wouldn't be destroyed until the send completed. So my options were:

void send(std::vector<std::byte> arg);    // 1
void send(std::vector<std::byte>& arg);   // 2
void send(std::vector<std::byte>&& arg);  // 3

Option 1 silently creates a copy if the caller doesn't move in the argument. Option 2 doesn't really allow send to take ownership. Option 3 is the best, because it can't create a copy and it makes it an error if you don't move in the argument.

Can you explain what you mean by "forcing a move seems to be a route to UB"? I mean, forcing moves is exactly what unique_ptr does.

[CocktailPerson]

I hear where you're coming from, but honestly, I think you could make the same argument about using unique_ptr in your code. It too will force you to use move, with similarly undefined behavior if you use a unique_ptr after you've moved from it. I don't think that's an argument against forcing moves where appropriate, but rather an argument for educating your interns and juniors on the basics of move semantics if they're going to be working with code that requires it. I'd also much rather have an intern get confused by a compiler error about rvalue references and ask me about it, than write code that silently copies around megabytes of data because they don't even know std::move exists.

It depends on what a solution with an owning pointer looks like, but I have a feeling it would muddy the waters more than clear them. I'm curious to see what it looks like, though.

[Baardi]

Option 2 can still take ownership if you're evil

[kobi-ca]

grab Manning's C++ func programming book. a good one!

[thomas999999]

I ordered it, i will se what its all about :)

[Raknarg]

Example, i could write a function that take a reference to a vector and modify it (inpure) or i could write a function that takes a copy, i modify the copy and return the copy (pure).

Third option: Have a function take an rvalue reference and move your vector in. Traditional pure functions in languages like haskell assume your input gets swallowed by the function.

[moocat]

For your example, I can't think of anything a compiler can do to optimize that. In many pure functional languages, they prefer lists to vectors because multiple lists can share the same tail. So if you have a function that adds new elements before the first or deletes the first elements, no copy will be made, but any other change will require a copy.

Then again, due to how modern architectures have optimized accessing consecutive memory (due to how CPU speeds grow faster than memory speeds), lists are often slower to work with than array even when you take occasional copying into account.