A brief discussion on major road blocks in Haskell, helpful resources, installation, list comprehension, and recursion all in one blog.
What are, in your opinion, the major stumbling blocks in learning Haskell?
Beware of Mental Traps!
It is an indisputable fact (at least in my book) that Haskell can be a pain...at first.
The shift from a C++ background to Java and Python was not as troublesome as my transition to Haskell. However, for those who did not struggle, congratulations! To start, Haskell is different from any programming language I have ever learned. As stated in my previous blog (Haskell's Got Style), Haskell is a functional programming language but my devotion to imperative OOP style programming crossfires with Haskell. You can say it's such a hassle (no pun intended).
When approaching Haskell, especially when writing recursive definitions, remember that discrete mathematics and Haskell are partners. Many formal proofs in discrete apply recursion. Learning how to formulate a proof in discrete is a gateway to constructing a program in Haskell (especially from scratch). Again, Haskell is heavily math-oriented and can be overwhelming at first. Diverging from an imperative style of programming mindset is the first major step. For instance, don't focus so much on where the location of a variable is stored. You'll fall into a mental trap. In Haskell, variables are names of values. Know that a function can be used as an argument and can be seen as a value. To be sure, it's a 180 from imperative programming but we'll get there.
Another roadblock is Haskell's lazy evaluation. But what do we mean by lazy? Graham Hutton, author of Programming in Haskell , describes the lazy evaluation as " the mechanism used to evaluate expressions in Haskell." Below is a simple example that demonstrates Haskell's lazy feature.
We Love Lazy Languages
Haskell is lazy. To illustrate this concept, consider the following pseudo code below:
if(a & b)
{
// do something...
} Similar to C++ and Java, Haskell will execute the code within the block if and only if 'a' and 'b' are true. In short, if 'a' and 'b' are true, "do something." However, if 'a' is false, we immediately know that the condition is not true. There is no need to evaluate/execute "do something." Better yet, we don't need to evaluate 'b'- saving us time. Indeed, a major advantage. By excluding unnecessary computation, it prompts a better execution time. Laziness pays off (in this sense). However, there is a downside. Although the lazy evaluation ensures that no unnecessary computation will be performed and terminates the program when necessary (like our pseudo code above), it's difficult to understand which code is evaluated. The execution order/time of a program is unpredictable.
In his book, Programming in Haskell, Hutton provides a perfect example of this:
Lets assume that n has a value zero, this expression can be evaluated by first performing the left-hand side of the addition
n + (n = 1)
= { applying n }
0 + (n = 1)
= { applying = }
0 + 1
={ applying + }
1 or alternatively, by first performing the right-hand side:
n + (n = 1)
= { applying = }
n + 1
= { applying n }
1 + 1
= { applying + }
2 The final value is different in each case. The general problem illustrated by this example is that the precise time at which an assignment is performed in an imperative language may affect the value that results from a computation. In contrast, the time at which a function is applied to an argument in Haskell never affects the value that results from a computation (Hutton, Graham. Programming in Haskell p.213) .
Which external sources (videos, blogs, tutorials, etc) do you find most useful?
Useful Resources
There are many helpful books and resources on the internet. However, I found that
my top 4 must-reads/watch to be the following: 1. Learn you a Haskell for Great Good by Miran Lipovača 2. Programming in Haskell by Graham Hutton
3. Get Programming with Haskell by Will Kurt
4. Check out the Youtube channel Computerphile
All 4 resources illustrate ideas imperative to Haskell in the most simplest way.
For example, the channel Computerphile hosts videos that cover concepts relevant to Haskell. Computerphile's Fibonacci Programming video, anchored by David Brailsford, highlights the importance of recursion and relevance of Fibonacci applications to it.
Note, I've included the link below (under references) for Computerphile's Fibonacci Programming video.
How does Haskell compare to your favorite programming language?
I've included a simple coding example below that highlights key differences between my favorite imperative programming language and Haskell.
C++ code: Given an array, myNums[], the program assigns all the even numbers to the array myEvensNum[ ] and outputs to the console.
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
// insert code here...
int myNums[] {3,2,8,4};
int myEvenNums[4];
int j = 0;
cout << "Size of myNums: " << (sizeof(myNums)/ sizeof(int)) << endl;
for( int i = 0; i < (sizeof(myNums)/ sizeof(int)); i++)
{
if(myNums[i] % 2 == 0)
{
myEvenNums[j] = myNums[i];
j++;
}
}
//Lets print the list
for( int i = 0; i < j; i++)
{
cout << myEvenNums[i] << endl;
}
return 0;
}Output:
Size of myNums: 4
2
8
4
Haskell code: Takes a list as an argument and filters out all the odd numbers in the list.
The list then contains all the even numbers and outputs to the console.
-- what I learned: select_evens is our variable and takes in a
-- list and returns a list
select_evens [] = []
-- x is the head of the list and xs is everything after
-- if we take the current head and divided by 0, if it returns 0 -- then we know that it is an even number
-- then we keep that head in our list
select_evens (x:xs) = if x `mod` 2 == 0 then x:select_evens xs else select_evens xs From terminal:
ghci
:l hwLists.hs
*Main> select_evens [1,2,4,6]
[2,4,6]
Notice that Haskell can perform this task in 2 lines while C++ takes a lot more. To be sure, if we wanted to conduct the exact task as the Haskell code above in C++, we would need to make a few changes. Yes, it would take more lines. Why? The array is a fixed size in my C++ program. We could use a vector or dynamically allocate the array (if you'd like to study this further detail, here's a helpful link: http://www.fredosaurus.com/notes-cpp/newdelete/50dynamalloc.html).
The point of this exercise is to show that we have to worry about a few more things in C++ than we de in Haskell. In C++ we must know where the variable is stored and utilize the correct data type. But with Haskell, we don't have to worry about that. Furthermore, thanks to Haskell's "laziness", algorithms are more simpler and increases performance. I'm starting to like this language, aren't you?
However, we must consider the tradeoffs of both languages:
Strengths and Weaknesses
Below I've summarized a major difference that highlights what we observed in our previous example.
C++
It's really fast
has superior performance for both runtime and memory management
Tradeoff : C++ is an object-oriented language and as such has side effects, which makes it difficult to write correct code. But with Haskell, we can avoid side effects (except in things like I/O). Thus, our code is more likely to be correct when written in Haskell.
Haskell
A lazy language, and a functional programming language, in which side effects can be avoided.
simplifies algorithm
increases performance
Tradeoff: Becomes difficult when it comes to the order of call in a function (as explained in We love Lazy languages).
Type checker
By checking the code during development, we can catch bugs easily.
How to install Haskell?
Top 2 Helpful Videos that I found most useful for Haskell installation:
Here's a rundown of the link above.
1. Go to https://www.haskell.org/platform/
2. Download Minimal ( I downloaded the 64 bit)
3. Run the .exe (installer) file
Try out simple exercises: https://www.youtube.com/watch?v=02_H3LjqMr8&t=1330s
After you've attempted these exercises from the video and familiarized yourself with Haskell a bit, we'll cover recursion in detail. However, before we tackle this, we must first understand list comprehension in Haskell.
Lists and List Comprehension
Lets do a brief overview on lists.
A list in Haskell has a head and a tail. The head is the first element in the list and the tail is the last element. You may have seen it in this form: (x : xs), where x is the head and xs is the tail. In the example below, the function oddLists takes in a lists and returns a lists that contains only the odd elements from the lists and it does so recursively.
oddLists [] = []
oddLists (x:xs) = if x `mod` 2 /= 0 then x:oddLists xs
else oddLists xsWhat is going on here?
Base case: oddLists [] = [] tells us that if the list is empty, it returns an empty list.
Function: oddLists (x:xs) .... if the head of the list x % 2 does not equal 0 then we keep the head and do a recursive call to check the next element in the list. Else, we call the oddLists again and check to see if the next one holds an odd value. If so, we append that to the front of the list. There's a key point to the example above.
We're doing pattern matching. When we insert a value into the console (like below), it checks the first case. If the list does not match with the first case, then it moves onto the second case. In our example below, we wrote the input as [1,2,3,4], so it executes the second case. The non-empty list will match [1,2,3,4] to the our input definition. As stated earlier, x is the head of the list, so our program knows that 1 is the head of list. It then matches 2,3,4 to xs or the tail of the list. From there it executes our second case.
From terminal:
Prelude> :l lists2.hs
[1 of 1] Compiling Main ( lists2.hs, interpreted )
Ok, one module loaded.
*Main> oddLists [1,2,3,4]
[1,3]
Now that we have the basics of lists, we can cover list comprehension
List comprehension allows us to apply a function to a list in a simplified form (Hutton, Programming in Haskell p. 42). For instance, if we wanted to take all the elements in the lists and double the value, it can be done in one line. Remember when I said that Haskell is heavily math-based? We're going to apply comprehension notation in mathematics in the examples below because it's in symmetry with list comprehension.
Graham Hutton, author of Programming in Haskell, provides an excellent example (p.43):
List comprehension:
{x^2 | x ∈ {1 . . 5}} produces the set {1, 4, 9, 16, 25} of all numbers x2 such that x is an element of the set {1 . . 5}.In Haskell:
> [x^2 | x <- [1..5]]
[1,4,9,16,25]There're almost like carbon copies of each other except the notation differs slightly. Here's a break down of Haskell's notation (Hutton, Programming in Haskell p.47) :
Symbols Description
| such that
< - drawn from
x < - [1..5] the expression is known as a generator
An important feature about the generator that Hutton points out is its ability to have successive generators. The example below produces a list that contains all possible pairings of an element from the list.
[(x,y) | x <- [1,2,3], y <- [10,15] This produces the following:
[(1,10),(1,15),(2,10),(2,15),(3,10),(3,15)]Recursion is Your Best friend
In Haskell, recursion is your best friend. As stated in my previous blog, recursion acts as a basic mechanism for looping in Haskell. The function is simply applied within its own definition. You "declare what something is instead of declaring how you got it" (Lipovača, Learn you a Haskell for Great Good).
Below are a few things to note before looking over the examples on recursion:
Beware of assignments.
In a recursive solution, we do not use an assignment. Be careful about '=', it is not an assignment, it literally means equal.
2. Pattern Matching
Recursion is important in pattern matching and will be used more as functions become increasingly complex. However, keep in mind that even the most simplest function (like sum) applies recursion on itself.
3. Go By the Format
A format to follow when using recursion.
1. define the base case
2. state the second case if the base case fails.
4. Powerful use of Induction
Recursion prompts the powerful use of induction. "Defining functions using recursion allows properties of those functions to be proved using the simple but powerful technique of induction" (Hutton, Programming in Haskell p.10)
Below are examples that apply recursion. When I first attempted these functions as exercises in class, I had to keep in mind the format (as stated above) for recursion.
Each has a brief explanation above about what each function does.
-- point: is to check if the member exists in the list
member m [] = False
member m (x:xs) = if m == x then True else member m xs
-- point: append two lists together
append [][] = []
append (x:xs)(y:ys) = x:xs ++ y:ys
-- point: to reverse the lists
-- concatenate the head
revert[] = []
revert(x:xs) = revert xs ++ [x]
-- point: the less equal function compares each element from each lists and checks if the first is less than or equal to the other
-- only returns true if all the elements from list 1 are less than or equal to the second list
less_equal [] [] = True
less_equal (x:xs)(y:ys) = if x > y then False else less_equal xs ysA helpful feature in recursion is its ability to allow a function to apply more than one definition. The Fibonacci sequence is a perfect example to this (Hutton, Programming in Haskell p. 65) :
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)Don't forget to check out my next blog Peano not Piano as we continue on our journey to find helpful tools to makes Haskell less of a hassle.
Next week's Blog:
Bonus Blog for Window Users:
References
Comments