Functional Programming 101
Getting understand the basic and foundation of Functional Programming
Concepts of Functional Programming
Functional programming is simplifying the computation with functions and mathemetical concepts. To get a clear idea of how functional programming differs to other paradigms, see following comparision.
- Everything is a function.
- Functions are pure, stateless.
- Functions can be composed.
- Functions can be curried.
- Lazy evaluation of functions (define first, execute later when needed)
- Not fully compatible with hardware, so it is executed in imperative way.
Object oriented programming
- Everything is an object.
- Classes define object characteristics.
- Inheritances of classes, deriving the characteristics from the ancestors.
- Objects can change their states.
- Program is a sequence of executions / commands.
- Functions define a sequence of executions.
- Fully compatible with hardware.
- Everything is a function ( 1st-class function ).
- So data is also a function (which returns a constant value)
- Also, function arguments are functions
- Functions are pure. They are stateless.
Data in functional programming
Algebraic data types is a powerful concept of data types in functional programming. It allows your data to be of following.
- Generic type with parameter:
type List a = [a]
- Multiple-choice data,
type Color = NoColor | Red | Green | RGB int int int
- Self-recursive data type!
type Graph a = LeafNode a | Node a Graph
This concept makes type definition pretty flexible and highly semantic! This also works great with pattern matching which will be mentioned later on.
A good news is algebraric data types are supported by lots of languages nowadays.
Concept of Computations
To build up computation with isolated functions would not be as straightforward as imperative programming. All you may end up doing is compose a nested call of functions like:
However, this could grow into complexity very quickly.
Here come some fundamental laws which bring your code closer to imperative style while remaining highly modular.
Typeclass in functional programming is somewhat similar to
Interface in OOP world. It defines a prototype, then its instance has to define the logic.
Interface in OOP:
- Defines properties for the class
- Define methods of class
- Stateful, can store data
- Instance of an interface is a class
Typeclass in functional programming:
- Defines applicable functions for the data type
- Stateless, only defines the logic
- Generic to types specified by parameters
- Instance of a typeclass is a data type
Example, we can define a typeclass as follows. The definition only briefly describes the prototype of a Joinable, but without any implementation of such logic.
class Joinable a: join :: a -> a -> a
Then we can define
List as an instance of this Joinable class as:
instance Joinable (List a): join l1 l2 = l1 ++ l2
More than one types can implement this Joinable class too :)
instance Joinable (List a): join l1 l2 = l1 ++ l2 ... instance Joinable (Maybe a): join Nothing w = w join w Nothing = w join (Maybe a) (Maybe b) = Maybe (a+b)
So from example above, if a function expects an argument of type
Joinable, you can simply pass in either List or Maybe types since both are implmented as Joinable.
Functor is a primitive typeclass which you can applies
map on it.
e.g. [List] is a Functor, as you can do a List.map(...)
let ns = [1,2,3] map (*3) ns -- yield [3,6,9]
A map function is stateless. It takes only argument and returns the same type.
Monad is typeclass which you can applies
flatMap on it. FlatMap is, by the way, the implementation of Monadic bind function
e.g. [List] is a Monad. You can do List.flatMap(...)
let ns = [1,2,3] ns >>= \x -> [x*3] -- yield [3,6,9]
A flatMap (monadic bind) is stateless. It takes only argument and returns the instance of that class. So for List[Int], the flatMap takes an argument of type Int and returns List[Int].
Applicative is yet another primitive typeclass. Similar to Functor, you can apply a map function but the function is wrapped as an instance.
e.g. [List] is an Applicative. You can do following
let ns = [1,2,3] let f = [\x -> *3] -- mapping function is wrapped as an instance of a list f <*> ns -- yield [3,6,9]
Yet another type class, Monoid is simply a group which after applying monoid operations, they still remain inside the group.
So which are monoid signature operations?
Identity, return an identity value which is a member of the group. Append, appending two values which the outcome remains inside the group. Appending a value with identityshould never change the value. Concatenation, folding a list of values into a single outcome which remains inside the group too.
A monoid guarantees it never mutates outside of the group.
- Identity = transparent colour.
- Appending transparent colour to any colour never changes the colour.
- Concatenation of multiple colours still make up a colour. It never becomes something else.
Why so many concepts?
All these rules are not straightforward for new learners but they become more and more useful when you tackle with implementation challenges. Since every fundamental things inside functional programming world complies the laws, you can simply design each module as generic as possible and bind them altogether with the laws you learn. This makes the program very modular and structurally systematic.
Resources to learn more
To learn about Monad and Monoid, I highly recommend watching this nice video from Brian Beckman :
And nice readings below:
Which languages to choose from?
This article is entirely based on Haskell but there are still other nice functional languages like Scala or F# and more. For beginners learning to code in functional way, I would highly recommend starting from Haskell as it constrains a lot and forces you to only think in a pure functional way.