Week1: Haskell's Got Style

What is Haskell? Any advice before I embark on my journey with Haskell? We'll answer these questions in Haskell's Got Style. But more importantly, we'll cover key concepts pertinent to Haskell.

Introduction

Haskell is a purely functional programming language. Functional programming is a style of programming in which the basic method of computation is the application of functions to arguments(p.4). To put simply, functions can be used as arguments. How does functional programming benefit us? Given Haskell's ability to treat functions as values, the code is easier to debug and it's more concise. Furthermore, it prevents side effects. Meaning, it makes it hard to analyze your program for correctness. Haskell can guarantee that function(s) has no side effects, making it easier to prove that the Haskell program is correct.

How do newcomers learn functional programming?

Forget everything you know. Not completely, but your approach to functional programming will differ from imperative. Imagine driving an automatic car all your life and one day you have to drive a stick-shift car. You can't suddenly become Vin Diesel in Fast and Furious but you can start with first gear. Like every language we learn, we must understand it.

For starters, here are some new concepts you should look into:

I. Functions are first class objects:

I'm about to blow your mind. Functions can be used as arguments. Kaboom. Indeed, quite different from C++ and Java. They can return values from other functions as well. This feature in Haskell is quite powerful. It ultimately allows us to write one function to another function without doing any repetitive computation. As Will Kurt, lead data scientist and author of "Get Programming with Haskell," elegantly puts it, "It allows you to abstract out any repetitive computation from your code, and ultimately allows you to write functions that effectively write other functions."

Lets say we wanted to create a function that checks if a number is divisible by 2:

ifNumDivisibleByTwo :: Int -> Int
ifNumDivisibleByTwo thisFunction n = if n `mod` 2 == 0 then thisFunction n 
                             else n

Then, we create another function that doubles a number

     doubleNum :: Int -> Int 
     doubleNum n = n * 2

Create another function that will double n if its divisible by 2. Here we can put Haskell's powerful feature to good use.

    ifDivisibleByTwoDouble n =  ifNumDivisibleByTwo doubleNum n

As Kurt stated, we "abstract out" doubling and checking if its divisible by 2 into two separate functions. Then using Haskell's feature, we are able to condense all these tasks into one function. As I said earlier, Haskell's ability to treat functions as values makes the code concise and easier to debug.

II. Heavy use of recursion

Why is recursion so important in functional programming? It's the basic mechanism for looping in Haskell. In Haskell, there is no while, do-while, and for loops like in C++, Java, and Python. As mentioned earlier, Haskell is not imperative -it is functional. We have to explicitly state what the program is and how to do it. We'll dive deeper into Haskell's relationship with recursion in Week 2 (Recursion is Your Best friend under the blog title No Hassle Haskell) For now, we'll settle with an example that is universally known, the Fibonacci Sequence. To refresh your memory, the Fibonacci Sequence is used to calculate exponential growth (Kurz, Imperative versus Functional) However in programming, we'll use it to examine recursive functions.

From a mathematical point of view, here's what you'd typically come across:

    FN + 1 = FN + FN-1 <br>
    F2 = 1 
    F1 = 1 
    F3= ?

What does this entail?

We have our base cases F2 = 1 and F1 = 1. To find F3, we know that it is the same as F3 = F2 + F1. Both F2 and F1 are 1 and 1 + 1 is 2. Every Fibonacci is the sum of every 2 that precede it.

To find F4, we know that F4 = F3 + F2. Given F3 = 2 and F2 = 1, F4 would equal 3.

Following the steps above we know that the list will continue on like so: 5, 8, 13, 21...

David Brailsford, Professor of Computer Science at the University of Nottingham, emphasizes that "Fibonacci is a recursive function that can be de-recursed. Things that can be de-recursed are called Primitive Recursion." What does this do for us? Using the Fibonacci Sequence allows us to conduct for loops and is a great exercise to conduct recursive programs in Haskell.

III. Know Discrete

Save yourself the agonizing pain of pulling your hair out and learn discrete.

My first homework assignment in Computer Languages taught me that some concepts you learn in another class may apply heavily to the other. In my case, it was Computer Languages and Discrete Mathematics. Proving basic arithmetic operations by natural numbers(NN) and applying recursion in discrete was analogous to my first assignment in Computer Languages. I realized that many underlying concepts in Functional Programming were especially grounded in Discrete Mathematics. For example, to construct an algorithm in Discrete Mathematics for NN we must be precise and make specifications (Moshier, p.18). Below I'll show the symmetry between discrete mathematics and Haskell by adding snippets of discrete mathematics from Dr. Moshier's book on Contemporary Discrete Mathematics and Haskell code that applies the same idea.

The sum of m contained NN and n contained in NN is a natural number m + n, calculated by the following:

               m + 0 = m 
               m + k_next = (m + k )_next    for any k.

We're going to write a Haskell function that applies the same concept above.

     add :: NN -> NN -> NN <br>
     add O n = n <br>
     add (S n) m = S (add n m)

What did we just do?

1. We specified that the function add must take in 2 argument and return 1 argument.

2. State the base case. Like the algorithm for addition in discrete (m + 0 = m),we write out our base case: add 0 n = n.

3. Write (S n) m = S (add n m). This states that adding n and m is equivalent to the sum of the successors of n and m. For instance, 1 + 2 is S(S O) + S(S(S O)). This is known as Peano arithmetic but we'll dive into that late in the blog (see Blog titled Peano not Piano for more details). We know that 1 + 2 is equal to 3. By our definition of addition in the program above, it would equal S(S(S O)).

What is the point of this exercise?

To show that discrete mathematics and functional programming are equal partners. Many mathematical concepts learned in discrete mathematics illustrate the backbone of programming concepts. In turn, functional programming provides concrete applications. You can't grasp one without the other when it comes to Haskell.

So, save yourself the hassle and learn discrete.