Mountains of Monads

I'm still swamped in the midst of Write Yourself a Scheme in 48 Hours.

I recommend against kicking off on that project if:

• You do not know what a monad is and do not understand how they work. 
• You have not parsed anything before. 
• You do not know what an interpreter is. 

I started off this project with all those, and I am still struggling with the first one. 

As a result, I can reliably inform you that you can make a good start addressing the first two points with Monadic Parsing in Haskell by Hutton & Meijer.

I am still working on the last bit about interpreters, but we are getting there. 

Brackets, and How to Check that They are in the Right Order

The last exercise I started working on Write Yourself a Scheme was writing a function that reads a string, checks the brackets and returns a Boolean.

It's meant to check the following:

• The brackets open and close in the right order.
• Every bracket that was opened eventually closes.
• Every bracket that is closed has a matching opening bracket that was opened earlier in the list. 

The code for this exercise can be found here.

My first, and simpler, attempt only checks one kind of bracket. I take the string and filter out all the brackets, and work only on those.

checkparents :: String -> (Bool, Int) 

The Int in the tuple is the result of the following formula:

• If the bracket being looked at is an open bracket, +1. 
• If the bracket is a closed bracket, -1. 

The Bool starts at True at the beginning of the list and goes to False if the Int goes below zero or at the end of the list, if the Int does not equal zero. 

This reasoning follows from the fact that if the Int goes below zero, it means that there is a closing bracket that was not opened, as in the case where the first bracket in the list was a closed bracket. Similarly, once we have finished traversing the list, if the Int is more than zero, it means brackets that were opened were not closed. 

I tackled a more complicated version of the same problem with multiple kinds of brackets afterwards.

checkbrackets :: String -> Bool 

The reason why there is no Int is that I hit upon a better way to 'remember' the brackets that had already been 'seen'.

I wrote a helper function of the following type:

pairchecker :: (Char, Char) -> Bool 

This function checks that the first Char is an open bracket, and that the second is it's matching closed bracket. In every other case, it returns False.

Then I wrote a foldr that uses pairchecker and only retains brackets that were either never opened or haven't yet been closed. After the list is traversed, I check if the resulting list is an empty list.

checkbrackets can only be True if the result of the foldr is an empty list. If it's not empty, it means that there were brackets that were either never closed or never opened, and therefore has to be False.

Everything Is A Monad

In my household, functors, applicatives and monads have been bad words for some time.

I have since worked out that pushing me to Write a Scheme Interpreter in 48 Hours was to get me to learn more about monads.

I'm struggling a little with understanding the bind operator and how it works. I'm somewhat familiar with do notation, but I am not quite there yet with the IO monad either.

I am currently reading Learn You A Haskell's section on monads as well as working through a handful of basic exercises from How to Design Programs to familiarise myself with Scheme and it's syntax.

This thing is going to take me much more than 48 hours. :P

Write Yourself a Scheme in 48 Hours

The Programmer Bear told me shortly before Christmas that he thought I was ready to tackle Jonathan Tang's tutorial to write a Scheme interpreter.

This was great news for me because I was pretty keen earlier on when I first heard about it, but not understanding what an interpreter actually does put a damper on that.

I am in the midst of the second chapter now, and so far it's pretty good. It touches a fair bit on topics that I want to learn more about, particularly IO and monads.

The Skyline Problem

I have been working on this problem for a few days, and have accumulated 3 different approaches, nearly a dozen tests and a few hundred lines of code.

(This article by Brian Gordon is a good one if you don't know what the skyline problem is.)

My first two approaches were different formulations of creating a list of rectangles that did not have any overlapping bits.

This was complicated by the fact that I could not and still can't write a function that works something along the lines of:

function :: [Rectangle] -> [Rectangle]

function = foldl helper []

In this case, the helper function is meant to consume the original list of rectangles one at a time and produce a list of rectangles that don't have any overlap. It traverses the list only once, and from that you can do a mapping to produce either the area under the line or the list of points required to draw the skyline.

My most successful attempt requires transforming each Rectangle into a list of tuples:

xheight :: Rectangle -> [(Int,Int)]

xheight (Rectangle left right top) = map (,top) [left .. (right - 1)]

And then taking the maximum at each x-coordinate.

I still have a couple of edge cases that I need to work through to make it work perfectly -- unless I further down the rabbit hole than I currently think I am -- but I am getting closer.

This is pretty much my learning process, punctuated by moments of hey, it passed all my tests, and followed by oh wait, that doesn't actually work.

PS If you are interested to see what I have done so far: May's Github -- see files skyline, nonoverlap and xRect.

Data.List

I'm reading through Learn You a Haskell's section on Data.List at the moment, and fiddling around with rewriting some of the functions. 

Some are harder than others. 

transpose :: [[a]] -> [[a]] 

This one was very hard indeed. After an entire day of bashing my head against the wall, I discovered a few things I didn't know about Haskell syntax before. 

For instance, I used to think that at the end of the list, there were infinite : [] : [] : [] and so you go because if xs in (x : xs) could be infinite, why not : []? 

Things I try to do for each of the functions I'm rewriting: 

1. I try to figure out the type on my own. So far, this one seems to go fine.
2. I write it / bash my head against the wall. 
3. I import QuickCheck, and write a test to compare my version versus the Data.List version. e.g. 
• testx a l = x a l === Data.List.x a l 
• It is incredibly handy not to have to write something to test your functions on. When I was learning C, that was rather annoying. 

I will know that I am a true Haskeller...

...when I start importing at least 5 different library things at a time.