- What is Functional Programming?
- functional programming is not…
- why ‘functional’ then?
- helicopter view: the big picture
- benefits of functional programming
- limitations of functional programming
- learning guide for functional programming
- why the weird new terms?
- The Concepts
- Category Theory
- Pure Functions
- Monoid
- Why bother with Monoids
- Functor
- Monad
What is functional programming?
What functional programming is not.
Python uses functions such as len("my string") in place methods such as "my string".len() however this has nothing to do with functional programming. Functional programming is about ensuring that functions and/or methods are functions in the mathematical sense of the word.
Coding so that all functions behave as mathematical functions, means not permitting the code to use values that could change between calls to a function to change. The only values that can ‘vary’ between two different calls to a function/method. are the parameters to that function/method.
Functional programming not about the things that are done, it is things that are not done:
- variables cannot be changed, making the name ‘variable’ a misnomer
- to be ‘pure’ functions, functions can have no ‘side effects’ and cannot use variables values other than those passed as parameters
There is a great line by ‘Uncle Bob’:
If we have made any advances in software, since 1945, it is almost entirely in what not to do. ….. functional programming: don’t use assignment
Robert C Martin.
Why ‘Functional’ then?
The functional comes from the mathematical definition of a function.
Functional programming is programming using only ‘pure’ functions, and only immutable data. A pure function is a function that when called with the same parameters, will always return the same result, regardless what has occurred previously.
Only immutable data, means each ‘variable’ can only ever be set an initial value, and then never changed. Invariant variables. The concept is so different that the name is a contradiction.
These restrictions change programming. To code within these restrictions, some new ‘functional programming concepts’ must be introduced to make functional programming workable.
Functional programming is programming within these specific restrictions, but using additional concepts introduced in order for the restrictions to be work.
A functional program accepts input data, and performs a computation with that data which results in the output data. The entire program can be considered a function.
Imperative Programs Vs OO vs Functional Programs
The main alternative to ‘functional programs’ are called ‘imperative programs’. As a ‘imperative’ program can still be a completely satisfactory program, ‘non-functional’ is not really an appropriate label.
An OO (Object Oriented) program, can be imperative or functional.
As stated above, a functional program is more about the things are not done. No side effects, all values immutable for example. However, it is not about a complete elimination of side effects etc, it is more about avoiding these things whenever possible. Many programs written as ‘functional programs’ do at some points, include some code that is not strictly pure functions.
Helicopter View: The Big Picture
An imperative program is created as a set of instructions for the computer to follow. These instruction ‘build’ the result of output of the program. The meaning of imperative is authoritative commands. The program analyses the steps need to produce the result, and provides the instructions for the computer to follow.
A functional program enables transforming the input, into the output, through declarations of functions from which the transformation can be enabled. There is a flow from the data starting in the form at the time of input, and being transformed to end up in form required as output.
Benefits of functional programming.
Clean simple code. Lots of information on the benefits can be found by a search ‘benefits functional programming’. It is a large topic. so just to say having, adding the ability to solve a program using a functional approach is clearly better than not having that skill.
You don’t need to code in Haskell or a pure functional language to apply functional programming techniques. Functional programming techniques can benefit all code.
Even the Python web site has a section on functional programming, and Kotlin has specific features for functional programming, and libraries to enable more ‘pure’ functional programming.
Limitations of Functional Programming.
A clear indicator of a function that must have side effects is that there is no return value. What would be the point of a function with no return value if there are no side effects?
Now consider the classic “hello world” program! In practice, updating a database or producing other output all can be described as ‘side effects’. Some parts of program require side effects, which means the entire program will not be pure functional. The actual goal is to have all possible code than can be pure functional. As this link reveals, function code can be far easier to read.
Learning Guide For Functional Programming.
Learning functional programming is somewhat like learning to drive:
- Everybody can learn to do it
- The principles can be explained in very short video
- When you know how, it seems hard to believe it took time to learn, but it does
The tip is, don’t rush. One concept at a time, and allow that concept the sink in before moving on.
The Concepts
Category Theory.
An FAQ would be ‘is it necessary to understand category theory in order to understand functional programming’?
People disagree on the answer.
In one sense, it may be better to ask:
- “do you need category theory before you start”
- “or can I just learn as much category theory as I need to understand as I go”
Understanding a monoid does effectively require at some level understanding the concept of a category theory. I think it depends on the individual which way is best. Do you gain the required concepts as you, or before you start?
Categories are pluralities of things that are in some way similar. Somewhat similar to a ‘set’ in mathematics, but being even more abstract, it possible to have a category which does not meet all criteria for a set. Types normally will normally each fulfil the requirements of being a category, but the concept is not fully interchangeable, as types have more requirements than does a category.
One way to think of it is a category is link an interface that will normally be implemented by sets and by types. This leaves a category as something you cannot instance, but lots of things you can instance will qualify. A category is an abstraction of anything meeting these two main requirements:
- a number of ‘morphisms’, which must at least include an identity morphisms
- composability of the morphisms
A morphism transforms one ‘thing’ into another (or the same) ‘thing’ within the same category. In programs, a function that obeys these rules is the tangible morphism. Note that a morphism is limited to returning the same type.
Composability of the morphisms, is that if there is a morphism (f1) that transforms ‘thing a’ into ‘thing b’, and another morphism (f2) that transforms ‘thing b’ into ‘thing c’, then there must also be a morphism that transforms ‘thing a’ into ‘thing c’ that can be created from a ‘composition’ of morphisms (f1) and (f2). This can simply be created by composing f2(f1(a)).
In Kotlin:
fun compose(first: (Thing)-> Thing, second: (Thing)-> Thing) = {second(first(it))}
The function compose returns a lambda which with takes two parameters of type: (Thing)->Thing, and return a result of type: (Thing)->Thing and is the combination of both functions. This makes both the parameters and results themselves function, as they are ‘morphisms’ of the category Thing.
Pure Functions
One way to look at pure functions, is to consider at memoisation.
Consider the function such as ‘log’ or ‘sin’. For any real number, it is possible to calculate the log() or the sin() of that number, but the calculation is not trivial. Prior to desktop computers, and even desktop calculators, people who needed to these calculations would often use ‘log tables’ also know as ‘mathematical tables‘. These printed tables provide an answer to these ‘functions’ by looking up a value in the table, with the table providein the the answer for that value. Junior school students learn memorise ‘multiplication tables’, simpler lookup tables, which return the result for a function with two parameters, again without any calculation. To be able to list all the return values for a function is to memoise (commit results to memory to save recalculation in future) that function, and this is possible for all ‘pure functions’, because they return a fixed result every time called with the same parameters.
A pure function must:
- return the same result whenever called with the same parameters
- have no ‘side effects’: no action other than the calculation of the result
Monoid
Definition
A monoid is a computation operation for a type (technically an operation for a category, but in computing, types are the categories with operations) that enables combining things of that type. You could call the operation a function or an operator, but whatever the name, it performs a computation on values of a type that combines values of that type.
Two values of the type in, yields one value of the same type as a result.
An operation that obeys the rules of a monoid can be used can be used in particularly flexible and useful ways, which is why it is useful to determine which functions/methods represent monoids. Note that ‘+’ is not a monoid, but a family of monoids. Integer '+' is a monoid, a monoid is a computation for a specific type. Float + is a different monoid.
A monoid is computation meets these criteria:
- the two parameters, and the result must be the same type
- there must be an identity value for the operation
- associativity – can group any data
Parameters and result of the Same Type.
Consider integer addition, which qualifies as a monoid. 3 + 2 = 6
All the values were integers, so criteria 1 is met.
There is an identity value, zero (0), so criteria 2 is met.
(1 + 2) +3 == 1 + (2 + 3) is correct, so associativity holds and rule 3 is met.
Note, integer division in python returns a float, so breaks rule 1 and thus no go. In Kotlin, integer division does return an Int, so it passes this test. But (1/2)/3 != 1/(2/3) so there is no associativity. Also note that string concatenation is associative since:
(“ab” +”bc”) + “de” == “ab” + (“bc” + “de”)
even though unlike addition, the order of the values in the combinations must be retained.
The must be an identity value.
There must be some value that means ‘no change’. For integer-addition (as well as most other addition monoids), the identity value is zero. Note that the python string-addition monoid has an identity value of an empty string. For integer multiplication, or integer ‘raise to the power’, the value is 1.
Associativity.
3 + 2 + 1 = (3 + 2) +1 = 3 + (2 + 1)
This ability to complete any step at any time allow the work of applying a number of monoids to be assigned to different ‘workers’. Consider:
35 + 53 + 22 + 11 + 62 + 48
And imagine it needed a lot of computing power. One computer could do 35 + 53 +22 and another do 11 + 62 + 46 and then those two results added as the last step. This provides flexibility in how the work is done.
Why Bother With Monoids?
Hopefully, if familiar with ‘reduce’ in Python or in Kotlin, it is easy to see one use of monoids. But really how often do you use reduce() to perform calculations that need to multithreading? Is there more? It turns out there is. Consider the ‘fun compose’ example back in category theory? That compose is a monoid for the type: (Thing)-> Thing.
The real power arises when considering that functions can operate on code, not just data.
Links for background
Monoids in python. What is a monoid and why …
Functor (needs monoid?)
A functor is a container of data that provides for functions to operate on the data inside. In kotlin, this is through a ‘map’ method. Thus a list is always a functor as there is always a way to perform an operation of every element of the list.
More to come soon
Monad (needs functor)
don’t get me started on monads! ..well at least not yet, but soon
Python+Kotlin = Python++ 