Haskell: Session 2

Today I’ve read day 2 of the Haskell chapter and I’ve learned some pretty nice features of Haskell, which might be useful for the programming challenge idea I had the previous chapter. Here are the most notable features which stuck with me the most.

Cheat sheet

In the previous blog post I mentioned that it’d be nice to make some sort of a cheat-sheet for Haskell. Turns out there is already one (sort of):

https://learnxinyminutes.com/docs/haskell/

Anonymous functions

I don’t know much about anonymous functions besides the fact that they sort of… exist. I heard it’s a nice feature, but personally, I never had the need to use them so far. The book doesn’t go in-depth about this feature because the previous chapters for the other six languages also have them covered, which is a bummer because I did skip to Haskell immediately.

Haskell’s anonymous functions seem to be like the following:

(\ params -> function_body) input
e.g.
(\ x -> x + 1) 4
Output: 5

This creates an anonymous function with 1 input parameter, which increases x by 1. Its C# equivalent would be something like the following (not 100% accurate, I never used anonymous functions before):

delegate int TestDelegate(int x);

TestDelegate testDel = (x) => { return x++; }

var result = testDel(4); //returns 5

To add more parameters, you simply separate them with a space:

(\ x y -> x + y) 2 5
Output: 7

You can also assign anonymous functions to variables which is pretty much like a function definition. I guess the only difference is that you can then pass them as a parameter?

addOne = \x -> x + 1
addOne 2
Output: 3

Map and Where

The book mentions that Haskell has a map. Unfortunately, I’m new to the concept of mapping but one look at the code and I almost immediately figured out what it does.

map (\x -> x * x) [1, 2, 3]

What this seems to do is apply the anonymous function to each element within the list, making it a “square the list” function. It seems pretty handy, applying a function on a list without having to manually code a loop.

“Currying”

There seems to be a feature in Haskell which is called currying. See the following code example:

let prod x y = x * y

This multiplies x with y. Now, if I define a function which partially uses this function’s declaration…

let double = prod 2

…it actually means something like calling:

prod y = 2 * y

because the “2” substitutes the x. The C# equivalent of this would be roughly something like this:

int prod(int x, int y)
{
 return x * y;
}
int double(int y)
{
 return prod(2, y);
}

It’s a pretty interesting feature, but because of my inexperience with Haskell, I can’t think of a lot of practical applications.

Self-study

As with day 1, this day also has a self-study.

Write a sort that takes a list and returns a sorted list.

I decided to go with QuickSort as I’ve already seen a bunch of examples floating around on the internet. Admittedly, not 100% of the code is written by me but it’s easy enough to understand what it does.

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (h:t) = quicksort [x | x <- t, x <= h] ++ [h] ++ quicksort [x | x <- t, x > h]

This function takes a list of sortable items (Ord) and sorts them recursively. The quicksort pivot is always the first element of the list (which isn’t the smartest thing to do if the list is already sorted). Using list comprehension, the elements smaller (& equal) and greater than the pivot are separated. These lists are appended by using ++.

It’s amazing how the function is so tiny. No temporary variable declarations or anything, the code is straight to the point. For comparison, here is the (bloated) C# quicksort which I wrote for my programming class:

private T[] QuickSort(T[] list, int left, int right)
 {
 if (list.Length <= 1)
 return list;

T[] output = (T[])list.Clone();

int i = left, j = right;
 T pivot = output[(left + right) / 2];

while (i <= j)
 {
 while (output[i].CompareTo(pivot) < 0)
 {
 i++;
 }

while (output[j].CompareTo(pivot) > 0)
 {
 j--;
 }

if (i <= j)
 {
 // Swap
 T tmp = output[i];
 output[i] = output[j];
 output[j] = tmp;

i++;
 j--;
 }
 }

// Recursive calls
 if (left < j)
 {
 output = QuickSort(output, left, j);
 }

if (i < right)
 {
 output = QuickSort(output, i, right);
 }

return output;
 }

I have to manually loop through the variables to check if they’re greater or less than the pivot, and separate them accordingly. In Haskell’s version, list comprehension handles that for me. That’s extremely convenient.

Write a sort that takes a list and a function that compares its two arguments and then returns a sorted list.”

I modified my quicksort algorithm to accept two anonymous functions:

quicksort :: (Ord a) => (a -> a -> Bool) -> (a -> a -> Bool) -> [a] -> [a]
quicksort _ _ [] = []
quicksort lt gt (h:t) = quicksort lt gt smaller ++ [h] ++ quicksort lt gt bigger 
 where smaller = filter (lt h) t
 bigger = filter (gt h) t

When I input the following into the GHC, I get the following output:

quicksort (\ a b -> if (a <= b) then False else True) (\ a b -> if (a > b) then False else True) [4, 6, 1, 3, 2]
Output: [1, 2, 3, 4, 6]

Write a Haskell function to convert a string to a number. The string
should be in the form of 
$2,345,678.99 and can possibly have leading
zeros.
 ”

This solution is based on list comprehension. Haskell has a function called “read” which can convert a string into another type.

strToNum :: String -> Float
strToNum num = read [ x | x <- num, x /= ',', x /= '$'] :: Float

As a string really is made of an array of chars, I go through each character, check if they contain undesirable float characters (in this case, ‘,’ and ‘$’, and discard them. I specified the Float type for the read function but really it probably also works without it, as the function already defines Float as an output. Haskell is smart enough to figure that out by itself.

Funnily enough, to test this function I kept calling the following for a good ten minutes:

strToNum $2,345,678.99

…without the quotes around the input string. No wonder the GHC kept complaining about parsing a ‘,’.

Write a function that takes an argument x and returns a lazy sequence that has every third number, starting with x. Then, write a function that includes every fifth number, beginning with y. Combine these functions through composition to return every eighth number, beginning with x + y.

To be perfectly honest I didn’t understand this question due to my limited English, so I had to look it up. The solution is from here:

every3 x = x:(every3(x + 3))
every5 y = y:(every5(y + 5))
every8 x y = zipWith (+) (every3 x) (every5 y)

From what I understand, the first two functions generate an infinite list of numbers. The third function takes the two lists and “zips” them together by using the add function.

Use a partially applied function to define a function that will return half of a number and another that will append \n to the end of any string.”

half = (/ 2)

Input: half 4
Output: 2
newline = (++ "\n")

Input: newline "Hello"
Output: "Hello\n"

Partially applied functions seems to be easier than I thought. All I had to do was… partially apply the infix functions for division and concatting a newline.

Here are the self-study solutions inside zip: Haskell – Day 2

I’m slowly starting to get used to the language. I’m slowly thinking out how to program that lz2 decompressor. The language seems to prefer recursion over looping so I’m really hoping that coding a decompressor is possible at all. I’ll find out soon, hopefully.

Haskell: Session 1

As mentioned in my previous blog post, I decided to learn Haskell for my programming class. Why I decided on Haskell? Because mainly the syntax really caught my attention. It’s unlike anything I’ve seen before, and I would definitely like to explore its possibilities. Furthermore, I’ve also heard that Haskell is mostly used in academic situations rather than actual real-life practices, but that won’t stop me from learning such a different language.

The blog posts will be divided into “sessions”. Normally I was planning to do one blog post per day, but due to time restrictions and the high workload of my semester, I might have to cram multiple sessions into one post.

In order to get started, I decided to follow day 1’s instructions according to the book “Seven Languages in Seven Weeks”. I downloaded the Glasgow Haskell Compiler (GHC) from the download (http://www.haskell.org/ghc/), and ran ghci.exe. For now, that’s all I need.

The chapter starts off with very simple instructions using primitive types, inputted into the GHC console. It then transitions to strings & chars, booleans and finally, functions. I won’t go into a lot of details, else this’ll be one hell of a long blog post. There’s how numbers work:

Input: 4
Output: 4

Input: 4 + 1
Output: 5

Input: 4 + 1.0
Output: 5.0

Input: 4 + 2.0 * 5
Output: 14.0

So far, seems simple enough. It’s processing basic math, and once you start using numbers with decimals, it’ll start outputting the result with decimals also. The GHC seems to append decimals only when necessary, not excessively.

Input: 1.0 + 1.0100
Output: 2.01

Order of operations seems to work as expected – based on the real math world. Parentheses are processed properly as well.

Input: 4 * 5 + 1
Output: 21

Input: 4 * (5 + 1)
Output: 24

Onwards to strings and characters. Strings are represented using double quotes:

Input: "Hello"
Output: "Hello"

However, you can’t concatenate strings using “+”. Rather, you have to use “++”.

Input: "Hello" ++ " World"
Output: "Hello World"

Characters are represented using single quotes:

Input: 'a'
Output: 'a'

However, strings really are just built up from an array of characters. From my experience, this is similar to C#.

Input: ['a', 'b']
Output: "ab"

Onwards to booleans. Seems like booleans are expressed using “True” and “False” (without the quotes). Not much can be said about them.

It looks like Haskell is a strongly-typed language. I can’t do something like “1 + True“, or ” “Hello” + 1 “.

Assigning variables to a function in a local scope:

let x = 10

Declaring functions:

 double x = x * 2

Calling said function with a parameter:

double 5

Declaring above function with a type definition, which accepts and returns integers:

double :: Integer -> Integer
double x = x + x

Where the first “Integer” is the accepted parameter, and the second “Integer” being the return type.

Haskell seems to have pattern matching. From what I understand, it seems to function like some sort of an if/elseif/else construction before the function itself is even called. Here’s an example of a factorial function which at the same time is recursive:

factorial :: Integer -> Integer
factorial 0 = 1
factorial x = x * factorial (x - 1)

To me, this looks like “if the input is 0, then return 1. Else, if the input is anything, execute [code after “x =”]”. The order of the pattern seems to be important. If that third line (which is a “catch-all” pattern) were to be the second line, the pattern would always match said line, rendering the third line for the input “0” useless. I guess it saves you writing if then elses. If you wanted to reverse the pattern matching, you’d use guards:

factorial :: Integer -> Integer
factorial x
    | x > 1 = x * factorial (x - 1)
    | otherwise = 1

The format is basically this:

 | [condition] = [function]

If the condition isn’t satisfied, it’ll continue to the next guard. If that isn’t satisfied, it’ll continue to the next guard, and so on. It seems that you can use it as a base case for recursion as well, which is pretty nice.

Haskell seems to support tuples, which is basically a bunch of variables bundled together. I remember C# having a similar feature also (e.g. “Tuple<int, string>”). It can be used to bundle variables together without making a separate class for them. Tuples in Haskell seems to be bundled in parentheses, like so:

(var1, var2, ...)
e.g.
(1, "hello")

The feature that I find interesting the most is “list comprehensions”. I’ve never heard of this before. The only way I can describe this is “apply an algorithm to a list”. For example, here is an algorithm which multiplies each element in a list of 1 to 10 by 2:

num = [1..10]
test = [multiplied * 2 | multiplied <- num]

which returns: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Or here is an algorithm which lists all numbers above 5:

num = [1..10]
test = [abovefive | abovefive <- num, abovefive > 5]

which returns: [6, 7, 8, 9, 10]

If I had to write such algorithms in, say, C#, I’d have to start writing LINQ queries or custom iterators which would be a lot of manual work. It’s interesting how you can solve this problem in Haskell with pretty much a single line.

From here on, I’ll skip to the end – the self-study. Else this blog post is going to be even longer.

The self-study results I have included with this post as a zip: Haskell – Day 1

To me, it feels like information about Haskell is all over the place right now. It’s like exploring a strange new world without a map. I’m thinking that I might actually have to make a map – a cheat-sheet – in order to speed up my coding a bit, at least until I get used to the language, else I’ll have to repeatedly look up trivial things I keep forgetting about, such as how to write a function with parameters.

While we’re learning this new language, we also have to think of a programming challenge which could fit the programming language’s problem-solving capabilities very well. I haven’t thought much about it yet, but I had a rather impulsive idea which I think is really funny but cool at the same time – writing an LZ2 decompressor (or a decompressor for some other format). The challenging part would be reading a binary file, reading bits from certain bytes and applying a certain algorithm to the processed data in order to get a decompressed file. I’ll have to look into this to see if it’s actually possible or not, though. I’ll also have to get approval from my instructor. Maybe for testing purposes, I’ll start with an extremely simple compression format which is RLE.

To me, it feels like this blog post is a bit rushed/unstructured, but hopefully, my future posts will be of better quality.