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.

Leave a Reply

Your email address will not be published. Required fields are marked *