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.
Functional programming
• 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.
Imperative programming
• Program is a sequence of executions / commands.
• Functions define a sequence of executions.
• Fully compatible with hardware.

Key Features

• 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:
e.g. type List a = [a]
• Multiple-choice data,
e.g. type Color = NoColor | Red | Green | RGB int int int
• Self-recursive data type!
e.g. 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: f(g(h(x,y),z),w)
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

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

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

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]



Monoid

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 identity should 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.
Colours is a simple example of Monoid group. It has following properties.
• 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.