FSharp - Thinking a bit more functionally for a prime number calculator
For my second post on F# I’m sticking with simple examples, and I’m going to write a really basic prime number calculator. Again I’m writing this in linqpad as an “F# program”.
So what is a prime number?
“A prime number that is divisible only by itself and 1.”
A nice simple example then… this is not going to try to be a smart mathematical solution to this, its going to be a brute force approach because it will take more code to write, and I’ll have to iterate etc…
First of all, a few rules I’ve picked up on F# from reading various sources (primarily the brilliant FSharpForFunAndProfit) and experimenting this week:
- Everything is a function - Seriously everything, the language sort of forces you into this mindset
- Chaining functions is powerful - Piping the results of one function directly to another is brilliant
- Higher order functions are powerful - These are functions that can operate on other functions, it means common behaviour’s can be packaged together nicely, and not reused
- Functions in F# are much, much more succinct that C# - FSharp does not require the types of declarations that need to be done in C# to pass around functions, most stuff is inferred.
- I still don’t quite know what a Monad is - :)
The F# solution I came up with is:
- We declare our 3 functions that we need to check if a single number is prime.
- isDivisible = just checks that dividing 1 number against another has 0 remainder
- totalDiv = this one is the functional equivalent of a for loop, it iterates the numbers between 1 and x, and returns those that are divisible without remainder.
- isPrime = this calls totalDiv, and checks the result has a count of 2, if it does, by definition it can only be divisible by 1 and itself so is prime.
- These are our helper functions effectively, we could write this without those, but it just makes the code a bit clearer
- This joins our functions together to calculate all prime numbers between 2 and 10000 by:
- Generating a list of numbers in the range we care about
- Piping that to the map function, that calls isPrime and gives us a result
- Piping the results of that to a map function that converts our result to a string.
- Piping that to concat (the argument is inferred by the pipe)
- Piping that to print (the argument is inferred by the pipe)
There are some fairly interesting things emerging from this code. EVERYTHING is really a function, and you are encouraged to write very small functions, this leads to a world where everything is also composable. This is a very powerful difference between Functional and OO paradigms, where OO encourages composition in the form of objects, F# encourages composition in the form of functions. You can do some of this in C# by passing around Func
Another interesting thing here is that 3. actually just looks a whole lot like a lambda chain in C#. Thats because the Lambda functions in C# are basically a bit of functional declarative programming that C# developers can, and probably do use every day. So thats good news :).
With these thoughts in mind, I’ve thought of a small refactor that can be made to make this more functional still…
So what did I do? I changed the “totalDiv” function to take in a function, and renamed it to “matches”, I also changed the way it gets called in isPrime to pass the isDivisible function. So we’re then left with three very specific functions that each only care about 1 thing, and “matches” is now very general, we could pass it any function that takes two values and returns a boolean.