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.

Lists - Haskell

My notes here are not meant to be an introduction or guide to learning functional programming. These posts will assume you have a background in another functional language, or at least understand the concepts. Let’s get to it.

Lists in haskell must be of the same type and are declared with your typical [] literal notation.

List concatenation ++

[0, 1, 2] ++ [3, 4, 5]
>> [0, 1, 2, 3, 4, 5]

[0, 1, 2] ++ [3, 4, 'a']
>> Exception

-- Note strings are just lists of characters
['a'] ++ ['b']
>> "ab"

[0, 1, 2, 3, 4] ++ [5]
>> [0, 1, 2, 3, 4, 5]

Add to head of list :

'H':"ello Haskell"
>>Hello Haskell

0:[1,2,3,4,5]
>>[0,1,2,3,4,5]

Access an item in a list !!

[5..10] !! 3
>>8

"Hello Haskell" !! 4
>>'o'

Now that we’ve got the feel for things..chug these operators:

keyword input output
head head [0,1,2] 0
tail tail [0,1,2] [1,2]
init init [0,1,2] [0, 1]
last last [0,1,2] 2
length length [0,1,2] 3
null null [0,1,2] false
reverse reverse [0,1,2] [2,1,0]
take x take 3 [0,1,2] [0,1,2]
drop x drop 3 [0,1,2] []
maximum maximum [0,1,2] 2
minimum minimum [0,1,2] 0
sum sum [0,1,2] 3
product product [1,2,3] 6

Phew now that that is over… List Comprehensions! They give you the ability to manipulate, filter or what have you, a list/set in order to get a new set.

-- add 1 to x where x is [0..5]
[x+1 | x <- [0..5]]
>>[1,2,3,4,5,6]

ahhh yes that familiar notation from discrete math. I’ve missed you.

-- multi var LC's
[x+y | x <- [0,1,2], y <- [3,4,5]]
>>[3,4,5,4,5,6,5,6,7]
-- just what you'd expect
-- in comes a LC fizzbuzz
[if x `mod` 3 == 0 then "fizz" else if x `mod` 5 == 0 then "buzz" else show x | x <- [1..100]]
-- I had to google how to print a haskell int as a string "show <int>"
-- [if x `mod` 3 == 0 then "fizz" else if x `mod` 5 == 0 then "buzz" else x | x <- [1..100]]
-- throws exception since not all the same type are returning.

That’s it for today. Next time we’ll recurse through lists and I’ll cover this.

How to save a life.

git fsck --lost-found --unreachable

That’s it. That’s all it takes.

Let's get ready to Haskell.

##Haskell TL;DR
A functional, statically typed programming language with lazy evaluation, and a type system that has type inference.

##Environment Setup * Download the Haskell Platform * Download Atom text editor * Open up your terminal, let’s set up some necessary dependencies for atom Haskell plugins.

$ cabal update  
$ cabal install cabal-install //if prompted to update
$ cabal install hlint
$ cabal install ghc-mod
  • Next let’s install the plugins
apm install language-haskell haskell-ghc-mod ide-haskell autocomplete-haskell haskell-pointfree
  • Open your terminal; to configure the plugins we will need the path for the following:
$ where hlint
$ where ghc-mod
$ where ghc-modi
  • Open up Atom.
  • File->Settings->Packages
  • Click haskell-ghc-mod
  • Copy ghc-mod and ghc-modi paths into setting fields.
  • Go back to Packages, click linter-hlint
  • Paste hlint path into setting field.

##Test * Create helloHaskell.hs

doubleMe x = x + x
  • Open terminal
$ ghci ./path/to/helloHaskell.hs
$ ghci> doubleMe(2)
$ ghci> 4

That wasn’t too bad! Next time we’ll dig into the basics and try to work our way to this.

Hello world

After reading hundreds upon hundreds of blogs from different people within the software & science communities, I have decided to start my own. I’m doing it for a couple of reasons.

Several months ago I was inspired by Kyle Simpson to try and commit to doing something open source once a day. I think integrating software and science writeups will be a good way to mix up my daily side studies. Github Activity Also, I know what you are thinking, “sheesh not another person trying to simply fill up their github activity.” but it’s not like that. I promise (…resolve()). I’ve become more disciplined, have committed to finishing projects, and have learned a bunch. I’m really glad I’ve pushed myself to do it. Maybe I’ll write a post on that some time; not tonight.

The second reason is my current place of work, is awesome enough to provide an education budget, which I used on buying a bunch of books. Here are a few…

Real World Haskell
Quantum Computing For Computer Scientists (yikes)
Concurreny in C#
The Pragmatic Programmer - Hunt, Thomas
Applied Quantum Cryptography (yikes 2.0)

This site will be where I ramble about what I’m reading; hopefully improving my own understanding. And maybe getting others interested in learning about something new.

We’ll see how this goes. Maybe if writing regularly becomes a thing (and I get better at it) I’ll be more likely to write some new LearnXinYminutes articles.

One step at a time.