Final Haskell Project: A brief study in Parrallism

Nested List Processing

As we have learned previously in this blog, Haskell is a language where lists are very important and therefore unsurprisingly one of the most important issues that must be addressed when programming in Haskell is how exactly are operations applied to lists?

In order to see if we can find some of the issues with operations on lists, let's write a quick maximum function that takes a list and returns the max value of the list.

This is a pretty standard way to do this in Haskell, let's take a closer look about how it works.

Fist we must import the Data.List library

Next we can define a function and give it a type definition.

The first line of actual code reads: 

maximum':: (Ord a) => [a] -> a

You may remember this means we will be ordering something in this function. In this case we tell the function to take a list ([a]) and return a single value (a).

The next line simply takes the element of the list and sets it to the Lambda Variable x

Finally the line maximum' (x:xs) = max x (maximum' xs)starts at the head of the list and recursively goes through and finds the maximum value in the list.

So far this is nothing we haven't already done in this blog and so we can expect to have success in our simple maximum function. Here are a few examples:

Success!

 

And again nothing really surprising here.

So where does the problem come in? Consider this, what if we had a list of lists and I wanted to find the biggest value in the entire collection? What would I happen if I just gave our regular function a list of lists? Let's see!

So here is the same function with a list of lists being passed in, rather than a list of simple integers:

So what we would want to happen is have the function return a value of 11. This is the result when this method is run:

 

Shoot! That's not quite what we were expecting. Why was a list returned instead of a single integer? The way this method is currently written can not handle nested lists. It simply finds the list with the greatest number of elements instead of the highest value from any list. How can we modify this?

In Haskell a pretty popular way to handle these lists is to flatten them. This is done by using a method within the standard Data.List library called intercalate. This method takes a list of lists and flattens it down to one list. Here is how I decided to implement this in Haskell:

And here is the result:

 

Now we can observe the result of 11 that we might have expected from the first method. This begs the question, which is a better way to handle lists? Well that depends if you have nested list values and you want a simple maximum of any element in any list or sub-list then the method using flattening is the correct way to do it. However if you have data and you want to know which list has the most elements in it the first way with a non-flattened list of lists would be the correct approach.

This is the example I decided to look at for my final example of Haskell programming. Overall I enjoyed learning about this language even though it was far more challenging than I had anticipated. Functional programming requires a far different way of thinking than the traditional object orientated programming that I had been familiar with. It was an interesting study.

I hope you had as much fun reading this blog as I had writing it. 

That's all for now.

Haskell Week 9

Syntactic Sugar:

Syntactic sugar is a way of making code more concise which makes it easier to not only write but also easier to read. 

Haskell is notorious for using these little short cuts to make bulky code "sweeter" and easier to understand. For example in a number of examples in this blog the syntax I used was the syntactic sugar equivalent for longer less attractive code.

Here is one example of a map that we looked at earlier in this blog



As you can see I used a map to add one to each of the Integers in the list [1,3,5,7,9] thanks to the magic of syntactic sugar I was able to simply say map (+1) and it knew exactly what I was talking about. The way Haskell can do this is by taking my "sweet" version of syntax and converting it back to the clunky unappealing code. In this case map (+1) translates to \x -> x + 1 which simply makes a lambda and assigns it to the value of x +1.

Another "sweet" piece of syntax in the same example is the list itself. To make the list I simply put the numbers I want to be members and they are added to a new list. Magic right? Wrong! Syntactic sugar! Once again Haskell interpreted my list as (:) 1 ((:) 3 ((:) 5 ((:) 7 ((:) 9 [])) This is the longhand way of creating a list, it uses cons (constructors (NOT LIKE IN JAVA)) to add each element to an empty list until the list is no longer empty.

Other shortcuts (Most of which I have used):

You can let Haskell do a lot of the work for you specifically with sequences. If I were to write print ([1..4]) Haskell would know to return 1,2,3,4 because I set a start point (1) and an end point (4) it then understand the ".." to mean "fill in the blanks here" The longer way to do this would be to use the built in function called enumFromTo and call it on the tuple 1, 5 like so: enumFromTo 1 5.

Even such things as if-else blocks (which really uses cases) are generally written in the short hand. Which I find to be an okay way to do it as long as there is an understanding of the "unsweet" code behind the abbreviations.

Haskell Week 8

Exceptions:

Exceptions and the way we handle them in Haskell are very similar to the methods we use in Java. Exceptions can be thrown, caught, and handled.

Some of the most common exceptions in Haskell include:

isAlreadyExistsError
isDoesNotExistError
isAlreadyInUseError
isFullError
isEOFError
isIllegalOperation
isPermissionError
isUserError

I find that the error reporting is much more readable and helpful in Haskell then in some of the other languages we have looked at, such as Java, VB, C#, and Python.

Here is a little error that I was given when I tried to run a method without creating an instance of anything to be returned to the console:

<interactive>:22:1:

    No instance for (Fractional [t0]) arising from a use of `myDiv1'

    Possible fix: add an instance declaration for (Fractional [t0])

    In the expression: myDiv1 50 [1, 2, 5, 0, ....]

    In an equation for `it': it = myDiv1 50 [1, 2, 5, ....]

<interactive>:22:8:

    No instance for (Num [t0]) arising from the literal `50'

    Possible fix: add an instance declaration for (Num [t0])

    In the first argument of `myDiv1', namely `50'

    In the expression: myDiv1 50 [1, 2, 5, 0, ....]

    In an equation for `it': it = myDiv1 50 [1, 2, 5, ....]

<interactive>:22:12:

    No instance for (Num t0) arising from the literal `1'

    The type variable `t0' is ambiguous

    Possible fix: add a type signature that fixes these type variable(s)

    Note: there are several potential instances:

      instance Num Double -- Defined in `GHC.Float'

      instance Num Float -- Defined in `GHC.Float'

      instance Integral a => Num (GHC.Real.Ratio a)

        -- Defined in `GHC.Real'

      ...plus three others

    In the expression: 1

    In the second argument of `myDiv1', namely `[1, 2, 5, 0, ....]'

    In the expression: myDiv1 50 [1, 2, 5, 0, ....]

Not only is the error shown, but there are also possible solutions that are given to attempt to correct the error. I have found that these solutions are actually very helpful and often times lead to fixing the problem and producing working code.

Haskell Week 7

Concurrency vs Parallelism

According to the Haskell Documentation there is a distinct difference between concurrency and parallelism.


Parallelism is "a technique to make programs faster by performing several computations in parallel. This requires hardware with multiple processing units" (Haskell)

Whereas, concurrency "refers to techniques that make program more usable. Concurrency can be implemented and is used a lot on single processing units, nonetheless it may benefit from multiple processing units with respect to speed". (Haskell)

So what exactly is the difference?

According to Simon Mar, in his blog ghcmutterings, "a concurrent program is one with multiple threads of control" all of which operate on one processor and share that processors resources.

This leads to the question what is a thread?

Threads are contained inside of processes a process can have multiple threads all of which share the processes resources, but they are also able to accomplish goals individually. An application may have multiple processes, and these processes may spin up multiple threads. The key to this is they all happen on one processor.

The key distinguishing factor with parallel processing is that more than one CPU is needed.

There has been an extensive amount of research as to the benefits of parallelism.

I found Simon Mar's research to be very helpful in trying to understand this very complex and high level issue

http://community.haskell.org/~simonmar/par-tutorial.pdf    

Midsized program

For my midsized program I wanted show the implementation of a couple of different sorting algorithms.

The first sorting algorithm that I would like to implement in Haskell is the quick sort algorithm. Here is a little graphic about quick sort (complements of wikipedia.org).

             
Quick sort creates a pivot point and then compares each of the other elements in the array to that value and then to the values next to them until each value is sorted (as shown above). The way I went about this was by first thinking about how I would implement the quicksort algorithm in Java and that got me started on some pseudocode. Then it was a matter of writing the algorithm in Haskell based on some of the other principles in Haskell as discussed previously in this blog.

As I discussed earlier when you make a function you need to start by giving the function a name and defining the types that it takes and returns.

qs:: (Ord i) => [i] -> [i]

In this case I called the function qs and said that it takes an Ord input (Which is Haskell speak for something that can be ordered stands for Ordering) in this case it will be a list called i and says that each element in the list will maintain the same type it initially was. Very similar to functions we have seen in the past during this blog.

Next comes the actual meat of the algorithm here is what I came up with:

qs(x:xs) = qs[y | y <- xs, y <= x] ++ [x] ++ qs[y | y <- xs, y > x]

I like to think about this in three main parts.

Part 1:

qs(x:xs)

This part takes the name of the function and says that (x:xs) meaning that an element x is compared to each of the other elements in the array, noted as xs. This is a coding standard in Haskell.

The next section:

qs[y | y <- xs, y <= x]

This part says that the remaining elements in the list being compared is now known as y and if y is less than or equal to x (the current item being compared) it should be moved over one place to the left and then the rest of the list is concatenated to the end (++[n]).

The last part is:

qs[y | y <- xs, y > x]

and this is the oppositive of the previous section. It takes all of the xs currently being compared and then moves it to the right and attaches the rest of the list to the left side.

Now since this is a recursive function (meaning it calls itself again and again until each element of the list is sorted) we must have a way to get out of the recursion otherwise we would be stuck. This is as simple as saying qs[] = [] which means it will stop when there are no more elements to be compared.

Let's take a look at the implementation:

and here is what happens when we run it:

Success!  The list has been sorted.

The next algorithm that I will take a look at will be the Bubble Sort.

Once again here are a couple of diagrams that explain exactly what Bubble sorting is (courtesy wikipedia.org)

      

Basically the way bubble sort works is by starting at the beginning and checking to see if the first two elements are in the correct order and if they are it stays the same, if not the smaller one is swapped with the larger one. The slowly moves the largest ones to the end and the smaller ones to the beginning.

I have for another class (Bioinformatics) implemented a version of the Bubble sort algorithm in Java and so I know the general procedure for implementation however since this is Haskell I had to do a little more outside research until I was fully able to compose a working piece of code. However, I am glad I had to do some more research because that meant I learned a lot.

Previously in this blog I have talked about the map and filter functions of Haskell. I had to use something similar in this code but instead of using a map I had to use a variation of the fold method (which is a combining function) known as foldl. This tripped me up for a while because I was trying to map over the function but this was not working. I found a couple of very helpful articles on StackOverFlow that helped me understand the need for foldl vs mapping.

Once I understood a little bit more about the nuances of Haskell I was read to begin once again I started by giving the function a name and defining the types/

Like so:
bbs:: [Int] -> [Int]

This gives the function a name and says what type each element is passed in as and what the expected return should be in.

The next bit of code was:

bbs (x:xs) =  step $ foldl go (x,[]) xs where

This starts out the same way as above, comparing a piece of the list to the entire list. This is where I had to go on the Haskell documentation and look up the foldl syntax which includes the step and go syntax. This allows us to go through each element of the array next we will see how to compare them using a new function called mapAccumL or just acc as it is referenced. (documentation here: Documentation)

The next bit is the actual compasion:

go (y,acc) x = (min x y, max x y : acc)

  step (x,acc) = x : bbs acc

This took me a long time of struggling and research to come up with and I am not sure if it is the most efficient way but it seems to work! This section takes a look at each individual x and y pairing and sees if they are in the correct order. If they are it leaves it the same, if not it will reverse the order.

Let's take a look at the final implementation:

And the results:

These are the two examples I decided to explore and work with. I feel like I learned a lot and I really enjoy the syntax of this. It is very mathematical and laid out simply. It reminds me of the math logic from CS242.

Thanks for reading and bearing with the long post.

Stay tuned for more Haskell Programming 

Haskell week 6

This week my main focus was on exploring some of the more useful libraries in Haskell I was amazed at how many cool features there are in some of these libraries. I explored a couple of different libraries so this post is going to be somewhat varied topic wise, but I think it is worth knowing some of these odds and ends of Haskell.

 Data.List

I researched some Haskell documentation and decided to test a couple of the functions that fall under the Data.List library.

Let's take a look at a little section of code I wrote:

The first thing that we have to do is import the Data.List library (this is done in a similar way to java). Once we have the library imported we can begin to use the methods it contains. The next line of code defines the main function of the program and the "do" command lets us erm, well... it let's us do things (like printing). The first method is the concat method. It takes the given strings and concatenate them together in the order they were given. Next we use the intersperse method which takes two parameters a character and then a string. The first character is placed between each character in the second parameter. Next we use the sort feature (pay special attention to this!). Lastly, we use the sub-sequences method which takes a string and returns a list of the possible substrings.

Let's take a look at the outputs:

Are these the results we would expect? I think so!

 System.CPUTime

The CPUTime library has two methods that are associated with it. The first is getCPUTime which returns the number of  picoseconds of CPU time that are currently being used by the program. I think this is a very interesting feature of Haskell. The second method is the cpuTimePrecision which is the smallest measurable difference in CPU time that the implementation can record. 


Let's take a look at the implementation:

And now the results:

Very cool!

Data.Char
The next Library that I looked at was Data.Char this library has some pretty standard methods but they still can be very useful. It has the standard methods such as isAlpha which returns a Boolean, isDigit, also a Boolean and some other built in ones such as digitToInt and intToDigit.

Let's take a look:

And the results:

Although this might seem somewhat trivial it will become important when we move on to other concepts.

Data.Tree

I decided to take a look at the Data.Tree library because in many of my CS classes I keep hearing about Trees so I wanted to do a little bit of research and make a couple of trees in Haskell.

and here you can see a visual:

Just a surface level example of trees.

That is it for now. Stay tuned for my progress with Haskell.

Haskell Week 5

This week I have not made as must progress in the past with Haskell due mainly to studying for finals.

However, I did take the time to investigate some of the real world applications of the language.

It seems from my research that applications of  Haskell are mainly academic based. But some large companies such as Facebook and Google report that some of their in house tools are written in Haskell. Also a large banking company uses Haskell for some of their security features.

I was very interested in the security applications of Haskell but I was unable to find very much detail, perhaps unsurprisingly.

Haskell week 4

This week in Haskell I have started to look at two new aspects of Haskell programming that relate to list manipulation (surprise, surprise). These functions are map and filter.

Map:

Maps are very interesting because they are a quick and useful way to apply a function to each element of any list. For example if we had a simple list such as [1,3,5,7,9] and we wanted to add 1 to each of these values instead of looping through the list with a for loop, adding one to each value (i+1) and returning the list with the new values we can do this very quickly in Haskell (with one simple line).

For example:

This simple statement will give us the desired output of:

In this example I used a list of all Integers and mapped a function that added the Integer 1 to each element. Mapping can also be done to lists of type String. If we had a list of Strings such as ["Name", "Age","Sex",Social Security Number"] and I decided after the fact that I wanted at add a colon at the end of each element. Using a map this is how that could be done:

The syntax is done by using the map operation and then the "++" characters (which is the String concatenation operand in Haskell) and then placing the character we wish to append to the end in quotes (in our case ":"). We can see that we now have the output:

Filter:

Filters while similar to maps work by checking each element in list independently and seeing if it fits the criteria of the specified function. If the element falls into the criteria (the boolean True is assigned) it is added to a new list that will be returned once every element has been tested If an element does not fit the criteria of the function, it is not added to the final list that is returned. And it can be said to have been "filtered" out.

For example:

Say we have a list of elements [1,10,2,11,3,12,4,13,5,14] and we want to filter through this list and only return all the integers that are greater than or equal to 10. This can be done using a filter like so:

This would print out the desired output of a list that contains only elements that are 10 or greater. Output:

This is a very useful feature in Haskell since most things that we will be aiming to do involve lists in some way or another.

Stay tuned for more updates on my progress with Haskell!

Haskell Week 3

Functions:

This week I have been focusing on looking at functions in Haskell. Since Haskell is a functional language, functions are unsurprisingly a very important cornerstone of the language. Functions are different in Haskell than in Java, C#, VB and Python. However, in my opinion they are a lot more intuitive and follow a very easy to understand pattern and logic. For example let's take a look at a simple function: the factorial operation.

In Haskell we start by giving the function a name followed by the :: characters and then a definition of the type of parameters that will be given to the function and the type of output that will be returned.

For the above example the function name was "factorial" (very creative I know) and then we used the :: character and defined that the function would take an Integer as a parameter and then return (->) another "Integer".

Once the function is defined we can create an instance of it and assign a variable to represent the Integer parameter, in this case I called it "n". Then I used the built-in product function and said calculate the product of each number starting with number 1 and going through n represented as [1..n].

I enjoy this logic based syntax very much. I think it is not only easier to write but also easier to read and understand. Once the function is defined and then an instance is created we can print out the result, like so:

Once this program is compiled and ran we can see that we get the correct output:

This idea of defining a function will become especially important to me as I begin to work on my Mid-range sorting program.

Stay tuned for more updates on my progress with Haskell!

Haskell Week 2

This week I have been continuing my progress in Haskell. I enjoy experimenting with the language and I am happy to say that I have succeed in my goal from last week and I have found a plugin for eclipse that allows me to write Haskell code with all the power of eclipse.

Download link:
http://eclipsefp.github.io/install.html

This has been the most helpful step in my learning of the language because ever since I have been programming I have been using eclipse, now I am able to use the tools built into eclipse such as the quick complete and the quick fix features.

This week I have been focusing on the topic of Pattern Matching. The reason I am interested in this is because we have been working on the Pattern and Matcher classes in Java in my CS242 course. Pattern matching in Haskell looks different than most things I have seen before but it also very powerful and intuitive once you get started with it.

Here is an example I have been working with. We can start by defining the name of a function here's an example:

numToString (Integral x) => x -> String

This line defines a function named "numToString" and then defines an integer called x "Integral x" then we use the => characters to state the pattern that we will be using. The next section of the line "x -> String" defines that we will be looking for an integer x and then returning a corresponding String value. For example:

numToString 150 = "One Hundred and Fifty"

Then we can run this function in our compiler:

ghci>numToString 150
and this will return:
"One Hundred and Fifty"

However if we try to run this function on an integer that is not defined we will get an Non-exhuastive pattern exception stating that not all integers are defined on this pattern:

demo: main.hs:4:1-41: Non-exhaustive patterns in function numToString

Patterns can also be applied to lists and Tuples which is a very powerful feature that I am interested in exploring!

Stay tuned for more updates on my progress with Haskell!

This week in Haskell

When I was asked to select a language to independently study during this semester I wanted to not only do something that I had never seen or used before but also something that could potentially be useful to me later in my programming career. I have heard a lot about functional programming as well as some topics such as concurrence and parallelism. I started my research as to what language excelled in some of the topics I was interested in. I found Haskell and began reading some documentation and my interest was peaked.

My next step was to see if I would be able to set up a compiler on my computer as to help facilitate my learning of this language. Lucky for me there are numerous compilers available online and I decided that I would use the GHC compiler package that is recommended by Haskell's own website.

Download link:
http://www.haskell.org/ghc/

Once I downloaded the package I found it was extremely easy to set up. I simply ran the .exe provided by the Haskell.org and I had a command line style compiler called GHC as well as a very cool compiler that had a Graphical Interface called WinGHCi. Now that I was all set up it was time to begin writing my first couple of programs. I dove into a really well written (and free!) online book entitled Learn You a Haskell for Great Good! This resource is aimed at people who have experience in some object-orientated programming but are new to the idea of functional programming, so it was the perfect starting point for me.

Link:
http://learnyouahaskell.com/introduction

After I had read the first couple of chapters in the aforementioned book I was ready to begin programming in Haskell. I whipped out the "Hello, World!" program pretty quick and was so interested in doing more that I continued to write some other simple programs. I wrote a simple Fibonacci number generation using recursion and this helped me to learn a little more about the language. The way I have been writing programs is by simply typing them into notepad (as shown in my previous post) I am curious about exploring the option of finding an IDE that can help me format the syntax.

So far I have been thoroughly enjoying the process of learning something completely new independently from scratch.

Stay tuned for more updates on my progress with Haskell!

-Mike

Hello, World!

The Language that I have chosen is Haskell which is a functional language that was first developed in 1990.

Intern level program:

The Hello, World! program is generally the first program that is taught to someone who is learning a new language. In Haskell there is greater flexibility in the creation of this program than in some other languages.

To make my example of the Hello, World! program I opened up notepad and typed main = putStrLn "Hello, World!"

Then I opened up WinGHCi which is a GUI for the Haskell Compiler and I loaded in my helloword.hs (hs is the file extension for a Haskell Program!) and pressed run! Let's take a look at the results:

Success. Simple as that.

Stay tuned for more Haskell Programming.