Assignment 3 - Haskell

It's happening!!

Finally 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.