# Fundamentals of Functional Programming

## 1 The Four Progamming Paradigms

### Imperative

• `Programming paradigm` is a style of computer programming - different style approaching problems in different ways.
• There are 4 major paradigms:
• `Procedural/imperative`: a series of instructions that tell computers what to do with the input to solve a given problem. Eacg instruction changes the state of the operation, for example, change the value of variables.
• `Object Oriented(OO)`: objects are used to model entities in solving a problem.
• `Declarative`: each statement describes the problem to be solved. Such as SQL
• `Functional`: functions are used as the fundamental building blocks of a program. A series of functions accepting inputs are written to solve the given problem.

## 2 Functional Programming Basics

### function

• a function, `f`, has a function type
• for a function f: A → B
• the function type is A → B
• A is the argument type
• B is the result type
• A function `type declaration` can be expressed in this form:
```f:: Intger—>Integer
integers as arguments and gives an integer as a result.
```
• The set of inputs is called `domain`
• The set of possible outputs is called `co-domain`.
• For example: a function is defined as: f: A—>B where f(x) = x2
• The above function can be said the input in `domain A` produces output in `co-domain B`
• The domain and co-domain are always subsets of objects in some data type, for example, A: a set of real, B: a set of position real
• A function can also in the following form:
```f: {Ed, Alex, Dan, Tom} —> {1122, 3452, 1234, 7892}
Ed maps to 1122, Alex maps to 3452 etc
The domain and co-domain can be of different data types
```

## 3 Functional Programming Features

### Stateless and Immutable

• `Stateless`: a variable’s previous state is not tracked
• `Immutable`: variable values cannot change
• you cannot perform this in functional programming:
```a = 2
a = a + 4
```
• Contrast imperative style with functional style:

### Easy to write bug free, correct code - No side effect,Referential transparency

• `No side effects` : functions can only perform some calculation and return some results- no I/O operations, no global state changes, no database interactions. In multithreads, one thread's operations will not affect others. The order of function calls will not affect the results.
• `Referential transparency` : same parameters will result in the same results regardless how many times the functions are called.
• Easy to write bug free, correct code due to all the reasons above.

## 4 Function Application and Partial Function Application

### Learn It

• The process of giving particular inputs to a function is called `function application`, for example add(3,4) represents the application of the function add to integer arguments 3 and 4.
• `Partial function application` refers to the process of fixing a number of arguments to a function, producing another function of smaller number of arguments
• `Partial function application` in effect applying the function to produce new function that produce part of the computation:
• if you fix the first arguments of the function, you get a function of the remaining arguments, for example, the function f below:
```f: (x*y)—>W  becomes partial(f) * y—>W

Partial application gives a function partial(f), this function
then applied to the second argument y.
```

#### `THINGS we learned from the above diagram`:

• the function add3Integers has three integers as input and output another integer
• it actually only take one input at a time, for instance, the first input 3. This in turn produces a new function:
```(integer->(integer->integer))
```
• the above new function then only takes one input 6. This in turn produces another new function:
```(integer->integer)
```
• the above new function also only takes on input 9. This finally produces the resulting integer.

### Partial Function Application Examples

• Consider the function add3Integers again:
```type declaration: add3Integers:: integer->integer->integer->integer
function definition: add3Integers x y z = x + y + z
function application: add3Integers 3 6 9

Therefore, this partial application allows for a fixed input 10

The add3Integers applies to 6 then 9, then 10 to reach the final results.
```
• Haskell functions only take one argument/input at a time.

## 5 First Class Object, Higher order functions

### First Class Object

• `First-class objects` (or values) are objects which may:
• appear in expressions
• be assigned to a variable
• be assigned as arguments
• be returned in function calls
• For example, integers, floating-point values, characters and strings are first class objects in many programming languages.
• When a function is a first-class object, it means it can be an argument to a function or a result of a function call

### Higher-order functions

• A function is `higher-order` if it does at least one of the following:
1. takes a function as an argument
2. returns a function as a result

## 6 list Data Structure in Functional Programming

### Learn It: list and its common operations

• A list is a collection of items of similar type
```in Haskel, list can be defined:
>>>let studentList1= [“Tom”,”Ed”,”Alex","Dan","Dom"]
>>>let ids = [123,456,678,124,543,888]
```
• You can also define an empty list or add elements to an existing list:
```Define an empty list
>>> let myList = [ ]

Test if an list is empty
>>> null myList

Append to a list (add more elements to the end)
>>> studentList1 ++ [“Harry”]

Preppend to a list (add more elements to the front)
>>>[“Harry”, “Felix”] ++ studentList1
```
• List operations:
function usage output Note
tail tail(studentList1) [”Ed”,”Alex","Dan","Dom"] returns a list without the head
last last(studentList1) "Dom" returns a single item
init init(studentList1) [“Tom”,”Ed”,”Alex","Dan"] returns a list

myList=["cat","dog","zebra","merekat"]

2. tail(myList) returns ["dog","zebra","merekat"]

## 7 Define Functions

### Learn It

• To define a function, you can simply specify its name followed by the number of arguments and the function operations:
```a function take an integer and times it by 2
doubleUp::Integer->Integer   The type declaration
doubleUp x = 2 * x           The function definition

doubleUp::Double->Double     The type declaration has changed
doubleUp x = 2 * x           The function definition is the same
```
• To define a function takes a list as argument:
```map  f  []      =  []                  Empty list input, empty list output
map  f  (x:xs)  =  f  x  :  map  f  xs
```
```takeFirst:: [Integer]->Integer    The function takes a list of integers
takeFirst [] = Error "No data give"  some useful error message if list is empty

takeFirst xs = xs !! 0       Get the item from list xs at index 0
```
• another example:
```average ::  [Integer] -> Double
average [] = error “No data given”
average xs = fromIntegral(sum xs) / fromIntegral (length xs)
```

## 8 The three high order functions in list operations

### Learn It: map function

• `map` is a high order function that takes `a function and a list` and applies that function to every element in the list, producing `a new list`.
• Examples:
```>>>map (+3) [4,5,2,9]
[4, 8,5,12]

>>> map (*6) [4, 5,2, 9]
[24, 30, 12, 54]

>>>map (max 4) [4, 5, 2, 9]
[4, 5, 4, 9]
```
• An example with user defined function:
```>>>DoubleUp x = 2 * x
>>>myList = [4,5,2,9]
>>>map DoubleUp myList
[8,10,4,18]
```

### Learn It: filter function

• `filter` is a function that takes a a function that tells whether something is true or not, and a list and then returns the list of elements that returns true when applied the function.
• function declaration: (a->Bool)->[a]->[a] - returns a list(the last argument) from all member of a list (the second argumen) meeting the condition set by the first argument.
• Exmaples:
```>>> filter (>0) [-9, 8, 9, 2]
[8,9,2]

>>> filter (== 5)[-9, 5, 25, 12]
[5]

>>> filter even [-9,5,25,12]
[12]
```

### Learn It: reduce or fold function

• `reduce or fold` function takes a list and reduces it to a single value by applying a function recursively to the list until the list is empty: apply the function to the head and recursively apply the function to the tail of the list.
• `foldl` : fold left function
```foldl (-) 8 [10,20,30]

Operationally, this is equivalent to: ((8-10) -20)-30

foldl (/) 10 [3,18,30]
It is equivalent to:((10/3)/18)/30
```
• `foldr`: fold right function
```foldr (-) 8 [10,20,30]

Operationally, this is equivalent to: (10-(20-(30-8)))

foldr (/) 10 [3,18,30]
It is equivalent to: 3/(18/(30/10))
```
• Use fold function to calculate factorial:
```factorial n = foldr (*) 1 [1..n]
[1..n] is an iterative expression of a list of numbers
from 1 to n
```

### Learn It: high order functions, list processing and recursion

• We touched recursion earlier in `fold` function with list processing
• The nature of recursiveness of applying function to a list is if a function can apply to the head of the list, then it should be able to apply to the rest of the list, the tail.
• Example 1: `reverse` function:
• reverse (x:xs) = reverse xs +
• the (x:xs) notation is a way of expression a list with a head x and followed by its tail xs
• The above function applies the function `reverse` to the head of the list , then recursive calls made to the tail of the list.
• Example 2: `take` function
• the take function takes n items from a list and return as a list
• it is defined as: take n (x:xs) = x : take (n-1) xs
• It applies the function `take` to the head of the list , then recursive calls made to the tail of the list.
• Example 3: `map` function
• It applies add2 function to the head of the list , then recursive calls made to the tail of the list.

## 9 Function Composition

### Learn It

• `functional composition` : Combining two functions to get a new function.
• For example, a function can be used as an argument in another function.
```Given two functions:
f: A—>B and g: B—>C

The composition of g and f (g o f ) is a function.
whose domain is A , co-domain is C

Mathematically:
f(x) = x + 5 and g(x) = 8x
g o f = g(x+5) = 8(x+5) - the composition g of f
```
• Example 1:
• `not` and `even` are two separate functions
• notEven is a composition
```>>> notEven = not . even
```
• Example 2:
```>>> squared x = x * x
>>> addOne x = x + 1