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.

Programming in Haskell

This is the main textbook I'm using at the moment, though it's a little older. Seems to be the only Haskell textbook I have found targeted at people who haven't programmed before.

I'm nearly half way through. I would like exercises that are a bit meatier, a la the famed SICP, but otherwise it is pretty good. I don't think I have made so deep into any other programming textbook yet.
I hope to finish this one before the end of the month. Most of the chapters have taken me about 2 days so far, and there's only 13 chapters.

The Programmer Bear approves of what I'm learning, and has been supplementing my education with bits and bobs, like teaching me how to write tests for my exercises.

Switching Back to Vim

Exactly like it says on the cover.

The Ctrl + Alt key thing got too much for me pretty quickly. How do people who use emacs not get RSIs in their little fingers?

On the bright side, this is spurring me on to learn the Vim shortcuts more quickly.

Rewriting Library Functions

I've been busily rewriting a number of library functions at the behest of the PB.

(Formerly known as the Programmer Boyfriend, he shall henceforth be known as Programmer Bear. T-shirts and other goodies to come.)

Most of the functions I've been writing are meant to be applied to lists, such as qsort, drop and take, and are mostly recursive.

Overall, I find these exercises to be rather useful. They help me understand how these functions work, and give me tiny glimpses into 'real' programming.

Today, We Have Divided My Household

I switched to emacs today after the PB informed me that it doesn't have modes. 

So far so good. I like it better than Vim and it's annoying modes, certainly. 

There will be further reports on this matter. In the meantime, I appropriated the PB's hard copy of Learn You a Haskell for a Great Good and need to continue with my studies. 

PS This post is powered by mini oranges. 

Beginning My Induction into the Cult of Haskell

The Programmer Boyfriend (henceforth PB) is a card-carrying member of the Cult of Haskell. For the purposes of this blog, it is perhaps the most important thing to note about him. As far as he is concerned, Haskell is religion. Indeed, he speaks more poetically of Haskell than he does of his love for me. 

Naturally, my first attempt to learn programming involved Haskell. It failed terribly. It nearly put me off programming forever. A friend of mine, when told that the PB was intending to start me off with Haskell, informed me that I would either go crazy or become a genius. 

Then we moved onto Racket (with How to Design Programs and Structure and Interpretation of Computer Programs) and C (The C Programming Language). 

(I have not finished reading any of the above the textbooks.) 

After C, the PB figures that I would be much more open to Haskell, so here we are giving this another try. 

I will be reading/working through Real World Haskell and Learn You a Haskell for a Great Good concurrently. 

#1 Conversations

May: If I want to write a Haskell program in Vim, what ending should I put in the file name? 

PB: .hs 

May: Oh, you mean like dot High School?