## Programming Paradigms

- Imperative
- Procedural
- Object oriented

- Declarative
- Functional
- Logic

Imperative - sequence of tasks to execute, and while executing, things change state.

Declarative - say what stuff is. In functional programming, we describe things with functions.

## Functional Programming

What should our mindset be?

- Start to think about functions like they’re variables. We use them everywhere as easily as we use a variable.
- Functions are kind of the same thing as data
- Functions have types!
- Functional programming is really just a style. We can program functionally in imperative langauges.
- Think “nouny” not “verby”
- Recursion is KING

What is a function?

- Has inputs and outputs
- Referentially transparent

## Haskell

**Purely functional**- no side effects! Has referential transparency. Only have to look at a function, not the whole program. Good for concurrency.**Lazy**- only evaluates things when it needs to. Allows infinite lists, data structures become generators.**Statically typed with type inference**- types must match up at compile time. Haskell can guess what type you want.

## GHCI

Glasgow Haskell Compiler is most widely used compiler for Haskell.

The interpreter can load haskell scripts (.hs) and allows interactivity.

```
$ ghci
> 3 + 2
> 3 - 2
> 3 * 2
> 3 / 2
> 3 * (-2) # need the parens
> (3 + 2) * 2 # can use parens to change precedence
```

## Prelude

You’ll notice that commands in GHCI start with Prelude. This is Haskell’s standard library.

Some common functions in the Prelude.

- head
- tail
- init
- last
- length
- take
- drop
- elem
- zip
- map
- filter

## Lists

Think of them as linked lists, not arrays.

All elements of a list must be of the same type.

```
> [] # empty list
> [3] # singleton list
> 3:[] # singleton list
> [2,3] # 2-element list
> 2:[3] # 2-element list
> 2:3 # CAN'T do this
> 2:3:[] # can we do this then? YES!
```

## Defininig Functions

```
doubleMe x = x + x
addMe x y = x + y
isEqual x y = x == y
```

## Exercise - Scripts

Haskell scripts have the extension `.hs`

.

- Create a file in your current directory called ex1.hs
- Write a function
`addTwo`

which adds 2 to it’s input. Save. - Start GHCi with
`ghci`

- Load file with
`:l ex1.hs`

- Call your function

## Pattern Matching

Specifying pattern to which data should conform Define seperate functions bodies for different patterns Can pattern match on any data type Goes through patterns line by line, top-down

```
addTwo 0 = 1
addTwo x = x + x
```

## Types

Haskell has a strong, safe and static type system.

Type signatures

```
addMe :: Int -> Int -> Int
addMe x y = x + y
```

Type variables

```
length :: [a] -> Int
```

## Exercise

Given the following functions and their type signatures, use ghci to work out what the following prelude functions do.

```
succ :: Int -> Int
head :: [a] -> a
tail :: [a] -> a
max :: Int -> Int -> Int
maximum :: [a] -> a
not :: Bool -> Bool
```

## More on Types

Checking a type:

```
> :t not
not :: Bool -> Bool
```

New construct, type class:

```
> :t (+)
(+) :: Num a => a -> a -> a
> :t max
max :: Ord a => a -> a -> a
```

Some type classes:

- Num
- Ord
- Eq
- Foldable

## Strings

Strings are just a list of Chars. This means we can perform list operations on strings.

```
> ['w','o','r','d']
"word"
```

## Infix vs Prefix Operators

## Exercise

Implement the logical XOR function using pattern matching.

```
xor_pattern :: Bool -> Bool -> Bool
xor_pattern False False = False
xor_pattern True True = False
xor_pattern False True = True
xor_pattern True False = True
```

Could we reduce the number of lines?

Now think of a smarter way to implement it, using another prelude function.

```
xor :: Bool -> Bool -> Bool
xor x y = not (x == y)
```

## More pattern matching

We can match by an arguments **structure**, not just it’s value.

Can use the cons operator to match a list, but assigning a different variable name to the head and tail of the list.

Can also match for an empty list, or a singleton list.

```
length' :: [a] -> Int
length' [] = 0
length' [x] = 1 -- this line is not relevant
length' (x:xs) = 1 + length' xs
```

This pattern is very common.

Notice we don’t use the `x`

, can drop it and use `_`

.

## Recursion

Since we don’t have a looping construct in Haskell, we often need to utilise recursion.

- Base case
- Recursive case

Sometimes easiest to write recursive case first and just placeholder the base case.

```
append :: [a] -> [a] -> [a]
-- Base case
append [] ys = ys
-- Recursive case
append (x:xs) ys = x : append xs ys
```

Step by step execution of `append [1,2] [3,4]`

:

– Initial – Pattern – Result append [1,2] [3,4] = append 1:[2] [3,4] = 1 : append [2] [3,4]

append [2] [3,4] = append 2:[] [3,4] = 2 : append [] [3,4]

append [] [3,4] = append [] [3,4] = [3,4]

1:2:[3,4] = [1,2,3,4]

## Exercises

Write a function to calculate the factorial.

Think about:

- Using a base and recursive case
- What the base case should pattern match on

```
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)
```

Write a function to sum a list of Integers

```
sumlist :: [Int] -> Int
sumlist [] = 0
sumlist (x:xs) = x + sumlist xs
```

Write a function to reverse a list using recursion and the (++).

```
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
```

## Guards

We don’t have to just use pattern matching. We can use an if-then-else construct.

```
elem' :: a -> [a] -> Bool
elem' x [] = False
elem' x (y:ys)
| x == y = True
| x /= y = elem' x ys
```

### Otherwise

Can replace `x /= y`

with `otherwise`

here. `otherwise`

is just syntactic sugar
for `True`

, and is used as a “catch-all”.

## Higher Order Functions

A higher order function is a function that takes another function as an argument.

One commonly used higher order function is `map`

.

```
map :: (a -> b) -> [a] -> [b]
```

```
> map (+2) [1,2,3]
[3,4,5]
> map even [1,2]
[False, True]
```

Defining map is easy

```
map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map' f xs
```

`_`

used when we don’t care about the argument.

Sidenote: Chars are enumerable

```
> map succ ['a', 'b']
"bc"
```

### Filter

Like map, but more restricted.

Function it takes is `a -> Bool`

```
> filter even [1,2,3,4]
[2,4]
```

## Tuples

Tuples are a collection of elements. The elements can be of any type, and the tuple forms its own type.

Tuples are defined in brackets and can be of any arity.

Tuple length/size:

- 0 - unit
- 2 - pair
- 3 - triple
- n - n-tuple

*1 - not supported without extra package*

```
> :t (1,2)
(1,2) :: (Num a, Num b) => (a, b)
> :t ('a', "bc", 3, 4.0)
('a', "bc", 3, 4.0) :: (Num t1, Fractional t) => (Char, [Char], t1, t)
> :t ()
() :: ()
```

## Lambda Functions

Haskell supports lambda calculus to write unnamed functions.

```
> (\x -> x + 2) 2
4
> (\x y -> x + 2 * y) 2 4
10
```

## Example

**Create a list between min and max**

How would we do this in python?

```
def listCreate(min, max):
my_list = []
while min <= max:
my_list.append(min)
min += 1
return my_list
```

Let’s take some of those concepts and transfer them to recursion.

```
listCreate :: Int -> Int -> [Int]
listCreate minn maxx
| minn > maxx = []
| otherwise = minn: listCreate (minn+1) maxx
```

We have to declare the Eq typleclass. Haskell doesn’t wanna risk it!

```
myElem :: Eq a => a -> [a] -> Bool
myElem _ [] = False
myElem x (y:ys)
| x == y = True
| otherwise = myElem x ys
```

Will both of these work?

```
ghci> myElem "ab" "dabc"
ghci> myElem 'ab' "dabc"
```

Let’s write a subset method.

```
subset :: Eq a => [a] -> [a] -> Bool
subset [] _ = True
subset _ [] = False
subset (x:xs) y'@(y:ys)
| x == y = subset xs ys
| otherwise = subset xs y'
```

## Example

An example of translating C code to Haskell without necessarily understanding the algorithm.

```
int mccarthy_91(int n)
{
int c = 1;
while (c != 0) {
if (n > 100) {
n = n - 10;
c--;
} else {
n = n + 11;
c++;
}
}
return n;
}
```

How do we set a variable?

```
mccarthy91 :: Int -> Int
mccarthy91 n = mccarthy91' n 1
mccarthy91' :: Int -> Int -> Int
mccarthy91' n 0 = n
mccarthy91' n c
| n > 100 = mccarthy91' (n-10) (c-1)
| otherwise = mccarthy91' (n+11) (c+1)
```

## Example

Merge sorted lists

```
merge :: Ord a => [a] -> [a] -> [a]
merge [] y = y
merge x [] = x
merge (x:xs) (y:ys)
| x <= y = x: merge xs (y:ys)
| otherwise = y: merge (x:xs) ys
```

## Example

Quicksort (in-place)

```
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (pivot:rest) = (quicksort lowers) ++ [pivot] ++ (quicksort highers)
where
lowers = filter (<pivot) rest
highers = filter (>=pivot) rest
```

How would we remove duplicates?

```
...
highers = filter (>pivot) rest
```

## Good Resources

- LearnYouAHaskell
- Hoogle
- Standard 98 Report - https://www.haskell.org/onlinereport/standard-prelude.html

## More Important Topics

- Data constructors, value constructors (and their arity)
- Monads