# Assignment 3 - Haskell

25 Jun 2015Finally getting around to doing a write up for assignment 3 in Haskell.

The first problem up is

```
Write a function, insert, that inserts an integer into a
list of integers sorted in non-decreasing order and returns
the resulting list.
```

Well that’s not too bad. First, let’s write a signature for the function that isn’t required, but is a good practice in Haskell.

```
insert :: Int -> [Int] -> [Int]
```

We are telling the compiler that the function `insert`

takes a parameter of type `Int`

, another parameter, denoted by `->`

of type `[Int]`

(List of ints), and lastly, a result of type `[Int]`

. There’s no special notation for the typing of the result, it’s just whatever the last defined type is in the type signature.

Let’s write the code.

```
insert :: Int -> [Int] -> [Int]
insert x [] = [x]
insert x (y:ys) =
if x < y then
x:(y:ys)
else
y:insert x ys
```

Some pattern matching with if-else flow control (could also use Guards). The other “new” thing to note from my last post, is `(y:ys)`

. This is just a way to split a list. `y`

is the head and `ys`

is the tail. Simple as that.

Here’s the breakdown of what’s going on for each recursive call.

```
insert 10 [3, 6, 9, 11, 12]
else -> 3: insert 10 [6, 9, 11, 12]
else -> 6: insert 10 [9, 11, 12]
else -> 9: insert 10 [11, 12]
...
if -> 11:[12] base case is hit! return!
...
returns:
9:[11, 12]
6:[9, 11, 12]
3:[6, 9, 11, 12]
>[3, 6, 9, 11, 12]
```

The next problem builds off the last.

```
Write a function, sort, that takes a list of integers and
sorts them in non-decreasing order using the insertion sort algorithm.
```

```
sort :: [Int] -> [Int]
sort (x:xs)
| null xs = [x]
| not (null (x:xs)) = insert x (sort xs)
```

The new notation you are seeing above `| <conditional expression> = <code>`

is called ‘Guards’. They are a easy way to define how to handle different patterns. Also note, `| otherwise = <code>`

is how to handle any pattern not previously matched.

Breakdown of what’s going on.

```
sort [5, 0, 4, 3, 1]
[5, 0, 4, 3, 1] is not null
insert 5 into sort [0, 4, 3, 1]
[0, 4, 3, 1] is not null
insert 0 into sort [4, 3, 1]
[4, 3, 1] is not null
insert 4 into sort [3, 1]
[3, 1] is not null
insert 3 into sort [1]
xs is null, return [1]
---
returns:
insert 3 into [1]
insert 4 into [1, 3]
insert 0 into [1, 3, 4]
insert 5 into [0, 1, 3, 4]
[0, 1, 3, 4, 5]
```

Next problem

```
Write a function sqsum that takes a positive integer n and
return the sum of the square of 1 to n For example, sgsum 5
should return the result of 1*1 + 2*2 + 3*3 + 4*4 + 5*5.
```

Answer

```
sqsum :: Int -> Int
sqsum x
| x == 0 = 0
| otherwise = x*x + sqsum (x-1)
```

Only knew thing here is the ‘otherwise case’ I explained early. Here’s the breakdown.

```
sqsum 5
otherwise-> 5*5 + sqsum 4
otherwise-> 4*4 + sqsum 3
otherwise-> 3*3 + sqsum 2
otherwise-> 2*2 + sqsum 1
otherwise-> 1*1 + sqsum 0
returns
5*5 + (4*4 + (3*3 + (2*2 + (1*1)))
55
```

Last one.

```
Write a function less of the type int * int list -> int list so that
less(e,L) is a list of all the integers in L that are less than e.
For example, less (4, [1,2,3,5,6]) should return [1,2,3].
```

Answer.

```
less :: (Int, [Int]) -> [Int]
less (x, []) = []
less (x, y:ys) =
if y < x then
y:less (x, ys)
else
less (x, ys)
```

Breakdown

```
less (4, [1,2,3,4,5,6])
if-> 1 : less 4 [2,3,4,5,6]
if-> 2 : less 4 [3, 4, 5, 6]
if-> 3 : less 4 [4, 5, 6]
else-> less 4 [5, 6]
else-> less 4 [6]
less 4, [] gets matched, return []
1 : 2 : 3
[1, 2, 3]
```

And that’s it! It was fun getting back in touch with my basic functional programming mindset. Find a base case, write your patterns, and recurse. I’ve already finished the code for Assignment 4 in Haskell, just have to write up the explanations. Til next time.