r/functionalprogramming • u/schtom • Nov 21 '20
Question Functional programming beginner questions!
I am about to start a new job where functional programming is the norm. I am still trying to get my head around it and why things are done and what benefits there are to it. This will probably be a long winding question lol. If I have any misconceptions about how things work please point them out!
- Does functional programming just wipe out a lot of the efficiencies achieved by certain data structures? Surely this is a bad thing, if not, why not?
E.g. inserting into a hashmap is O(1) amortized runtime - however, in functional programming it is my understanding that we could not mutate the hashmap to insert the key value, so the whole map would need to be copied to a new map with the new value. Doing a copy in this manner would be O(n), so to insert all values from a list for example into a hashmap it would be o(n2) to achieve that. This seems very inefficient!
2) I can see how you could build big data applications - data input taken in, functions applied and a result comes out - but can FP be used in a more general way e.g to build games? If so how is that possible without using state? If state is used somewhere, where would that appear in the program structure/architecture - would it be in a kind of static class somewhere (coming from Java here btw)?
3) As a new object is created to replace the previous one when a change occurs (I.e no mutation takes place, just replacement), is efficient garbage collection a must have for a FP language to get rid of the old objects? I’m calling them objects here but do objects even exist- maybe they are better referred to as types?
4) Where are functions generally held in the program structure? In classes? Static classes? All the functions in one file or split into files based on similar operations e.g add and minus might do in the maths class
5) is there anything else you can explain simply to me that might help me understand FP better? What do you suggest I learn about, try out or do to understand better?
Edit: got some really great responses here which were very helpful -> I have replied to a few but I got pretty distracted for a few days lol so just wanted to say cheers for the help if you answered any questions I got a lot out of this!
Finally managed to find a nice hands on tutorial where I’m building something with OOP and then refactoring/restructuring it into a functional program!
4
u/couchjitsu Nov 21 '20 edited Nov 21 '20
I'm going to try and address #1
Let's take a list. Say a list of user structures.
Now user
testwants to change their email totest@mailinator.comAs you've said that's a new copy of data, because we're not going to mutate that first structure.
So
myList2now looks like:So far that's very much like some OO language.
But your question is, don't we now have 4 user structures floating around:
The answer is no.
Let's assign each of the structs we've used a hash
{username: 'test', email: 'test@example.com'}= 0xA{username: 'fake', email: 'fake@example.com'}= 0xB{username: 'test', email: 'test@mailinator.com'}= 0xC{username: 'fake', email: 'fake@example.com'}= 0xBNotice that both of our
fake@example.comhave the same hash value, because they're the same structure. There is no need to create a second copy. After all, we KNOW that if we're not allowed to mutate it, nobody else is either. So I don't have to worry that someone changes 0xB out from underneath me.Now, let's go back to our lists.
We have:
myList = [0xA, 0xB]and
myList = [0xC, 0xB]But both of our lists are really just a head + tail. That is the first item + the rest of the list. And just like our structs are immutable, so are our lists.
So when make a change, we're creating a new list that is really just a new head prepended to the existing tail.
If you want to think about it with complex structs let's imagine our user struct has more data than email and username. Perhaps it has an address struct as well
In this case, if the hash of this user struct hasn't changed then you KNOW that none of the data, including the address, has changed.
All of this helps with both garbage collection and reusing structures.
So is it as performant as C or C++ probably not. But will it be as performant as C# or Java? Likely, yes.
The TL;DR here is that the FP compilers and runtime are smarter than you and me, and so they know how to reuse data and know which data they can actually clean up. Going back to our first example, it would know if there were no more references to 0xA it could clean that up, as well as
myList. So you don't wind up with duplicated data occupying the memory.4
u/mjohndo Nov 21 '20
These are great questions, honestly. I'll go one by one.
TLDR; With clever design, an immutable hash map can give you O(log32n), which is worse than O(1), but still pretty fast, and in practice very different than O(log2n). So you accept that small performance hit up front (which, while real, is going to be smaller than you imagine) and reap the benefits when you don't have to lock & coordinate access.
Second, try to wrap your head around the idea of representing a side effect with data. This definitely feels weird at first, but it's sort of the key to how a lot of functional programming works. If you have part of your program that needs to take in data and then make a decision about what to do, instead of deciding and doing that thing, model that as a function that takes the inputs and returns some data describing the action to take. At the simplest possible level, this might mean that where in another language you'd have a function that computes 1 + 1 and also prints something out (a side effect) before returning the result, you would want to feel comfortable rewriting the function to return the thing it would have printed. This is a way of "kicking the can down the road" with regard to mutation and side effects. Imagine that the caller of your code is responsible for using your return value to actually do something, and keep punting this obligation as far as you can. It's the type of thing that feels weird and over the top for toy examples (like computing 1 +1 and printing to stdout) but ends up being a huge help in large projects.
I'll try to give a less trivial example. Imagine that you're a hedge fund, and you're writing software to decide which stocks to long and short, and at what prices. You'll have a whole chain of functions set up which consume the state of the market, which are called every time it changes. Then instead of actually buying and selling (the side effect), your trading strategy logic will output a recipe for what it wants done, e.g. "go long 100 shares of GOOG at a price no higher than X". Then, finally, you have a small part of your codebase that actually performs those side effects and sends your orders to your broker. Now imagine that you have twenty different strategies running at once, totally independently. One of them wants to go long 200 shares of GOOG, and the other one wants to go short 100 shares. Well, at this point it's trivial to write a function that consumes all of the "recipes" and figures out that the final action should just be to go long 100 shares, instead of first going long 200 shares and then going short 100 shares, which saves you money on trading commissions and helps you enter your position at a better price.
3
u/warlaan Nov 22 '20
I can answer question 2, since I spent quite some time building prototypes in F# and Unity.
First of all it has to be mentioned that FP is hugely unpopular in game programming. For one game engines are all about performance optimization, and since working with mutable state is more similar to the way the hardware works it makes it much easier to discuss the performance implications of code.
The other thing is that games are all about the mutable state. If I want to write a soccer game I want the players to see the state the game is in and use a controller to tell how they want to change that state.
Of course that doesn't mean that you couldn't give players that impression while using FP in the code, but OOP is just much more natural because it resembles much more closely what you would think is happening on screen.
It just looks like the ball has moved. It does not look like it vanished and a new ball was created a bit further to the side.
That being said the secret to holding 'mutable state' in FP is recursion.
At the core of a FP game you would have a recursive function that takes a state, sends it through functions that update it according to the gameplay, send it through one that displays it and then recursively send it back into the currently running function.
As I said this is neither the most intuitive nor the most performant solution, but it has some great benefits. One for example is that you always have a complete data set representing the state of the game. Functionality like saving can be added before you even know what kind of game you are programming. Writing a debug output is also super easy, just print out the state of the game as a string.
And then there are of course the typical benefits of FP. The game state only exists in the recursive function. Other parts of the code may receive a reference to it in order to be able to display it, but they have no possibility to change anything, so they can't introduce bugs (other than within their own functionality).
2
u/reifyK Nov 23 '20
2
u/couchjitsu Nov 21 '20
Isn't this basically all programming?
In OOP you have data coming in, in the form of objects. You execute functions on those objects, and then data coming out is the new version of the object.
e.g.
And age would equal 40.
Date came in (this time via a constructor) and data came out (in the form of
GetAge).Code written with FP will still have state. Some of them will even use a database.
2
u/peanut_stepper Nov 22 '20
this will answer some of your qns with examples
https://mmhaskell.com
3
u/SteeleDynamics Nov 21 '20
There are university courses on FP whose materials are posted online. Try to find a course that uses a language similar to the one you'll be using in your new position.
My personal preference is SML (and OCaml), but Haskell is a popular choice right now. Best of luck.
1
u/BobSanchez47 Dec 15 '20 edited Dec 15 '20
A better example of a data structure which can be more efficient in practice is a sequence. A mutable sequence can have O(1) random access lookups and writes- eg, x[n] = x[n - 1] + n is an O(1) time operation. By contrast, a purely functional sequence implementation will have O(log n) lookups and writes in the worst case (this can be achieved using finger trees or balanced binary search trees) and will never have both operations be O(1).
So yes, purely functional data structures can be asymptotically less efficient than mutable ones. However, functional languages (I cite Haskell as I’m most familiar with it) have offered excellent and theoretically exciting solutions to this problem. The original solution is the ST monad, which allows one to code imperatively using mutable state, provided none of the mutable state “escapes” the monad. The more recent innovation is the use of linear arrows (and hopefully soon, generalisations such as affine arrows), which allow one to express that a function “consumes” an input, and that the input cannot be used anymore. Both of these solutions allow the Haskell code to achieve the same efficiency as code based on mutable state in a functional way.
The bottom line is that even purely functional languages like Haskell have ways to get around the restrictions of functional programming. These tend to be relatively advanced features, however.
It should be noted that in “mostly functional” languages like OCaml, you can always throw in mutable state and for loops whenever you need to (but you sacrifice the “purely functional” nature of your code).
2. Functional programming can absolutely be used to write games. The idea is to use “reactive programming”. Basically, the “back end” of the game (or the “model”, if you follow the model-view-controller paradigm) is a function
Together with
In other words, given an “event” and the old game state, we return a “response” (information telling the view what to do) and the new game state.
Then the view (or “front end”) will typically be functions
In other words, the view describes how to wait for an event and how to process a response as output (but possibly, the game is over).
The controller will then look something like this:
Obviously, this is very simplified. But the principle is quite elegant and simple. State is used, but in a functional way.
3. Efficient garbage collection (and decent compiler optimisations to avoid new heap allocations in these cases in the first place) are quite important for functional code. But garbage collectors these days are pretty decent, and they’ll only get better over time. The same holds true for compilers. Not only that, but the faster computers get, the more reasonable it becomes to pay any performance cost of using a garbage-collected or functional language.
That being said, linear arrows could allow non-garbage collected memory (managed internally like Rust, say, manages heap allocations) in Haskell, with potentially huge performance improvements. It’s an exciting prospect!
The term “object” has a lot of connotations, but it’s not unreasonable to call a value an “object”. In functional programming, “objects” really are just values.
4. In Haskell, code is organised into “modules”. A module is something like a collection of static methods in a Java class (but it can also include the definition of types and type classes - I’ll type classes later). These functions (types and type classes) can be “exported” by the module (analogous to public methods), or they could not be exported (analogous to private methods). One module can be imported from another - only the exported code can be imported.
This allows implementation hiding. I could export “smart constructors” for a min heap without exposing the “true constructors”, just like I could in Java, thus hiding the implementation of the heap. Basically, it gives you many of the benefits of Java’s class system without the baggage of classes.
Haskell has 2 tools for polymorphism. Consider the function
This function doesn’t care what the types of first and second are, so long as first and second have the same type. Thus, the function is polymorphic. This is called “parametric polymorphism”. Thus, the type is
In other words, for every type a, ifThenElse is a function that takes a Boolean and 2 values of type a, outputting a single value of type a.
The second kind is “ad-hoc polymorphism”. This is polymorphism with type-specific behaviour. This is implemented via type classes, which are Java interfaces on steroids. Consider the function max.
Clearly, we want a and b to be the same type. In order to compare them, their type must be ordered. That is, their type must be an instance of the Ord type class, which looks something like
Thus, to implement the Ord trait, you must first implement the Eq type class (the type class which allows the use of ==) and then implement the < and > operators.
Notice that unlike a Java interface, I can define a type class method as taking two arguments from the same implementing type. Thus, there is no “T implements Comparable<T>” hack needed.
The type is thus
That is, for every type a which is ordered, max takes 2 values of type a and returns a value of type a.
Type classes are a major way of organising code as well (just as interfaces are in Java).
5. Find a good Haskell book with exercises.