Tuesday, July 17, 2012

Introducing fhck, a brainf*ck interpreter written in Haskell!

If you haven't heard of brainf*ck, you should totally check it out, because it's probably the coolest programming language of them all!

Also, probably one of the simplest...

That's why I decided to write an interpreter for it!

This is the product of about 3 days of work, give or take, but the sessions were long and I put a lot into it.

If you're a Haskeller reading this, please feel free to critique it (I'm sure it could be improved in many places)!

If you're not, please feel free to check it out anyway! I encourage everyone to play around with brainfuck a little bit because it's actually a  lot of fun.

If you're not familiar with the language, a quick look through brainfuck's Wikipedia page should help you to understand what's going on in brainfuck (it's not too complex).

With the interpreter, you can write a file, say thisisbf.b, containing the classic "Hello, world!" brainfuck program directly from the wikipedia page:

and pass it to the interpreter:

on Windows:
$ build\windows\fhck.exe thisisbrainfuck.b
or Linux (or presumably Mac OSX, though I haven't tried):
$ build/linux/fhck thisisbrainfuck.b
...and it should print "Hello, world!" to your console!

Neat, right? (I think so!)

Download link/source is located here: fhck 1.0


Wednesday, July 11, 2012

99 Haskell Problems #13: Run-length Encoding

I've been working on The Ninety-Nine Haskell Problems lately, and I've come across a particular one that seems to be practical, and was a lot of fun to implement!

The 99 Problems start out with a lot of list-based exercises, and eventually you're asked to build up to a point where you can implement a function that performs Run-length encoding on a String. Basically what this means is, if we have a string, say "aabbcccd", we'd group together the adjacent, identical characters, count them, and then output the characters along with their counts in a new list.

Thus, the previous example "aabbcccd" would output something like this: a2b2c3d

A couple of the 99 Problems ask you to implement this indirectly, meaning, actually group the identical characters into sub-lists and count the length of those lists. This is fairly trivial, making use of Haskell's built-in function group, which takes a list and separates it in exactly the manner we would need in order to get sub-lists of adjacent identical values.

The real fun came in Problem 13, where it asks for a direct implementation of the run-length encoding algorithm, meaning, we're no longer allowed to split up the groups in the way that we were before. Additionally, the problem asks that we use a data wrapper on each ending value so we are able to discern Single values (example in above: d) vs Multiple values (ex: a2).

Here's what I came up with:

Let's take a look at this.

So, first I defined a new data type called Count that can be either a Single that contains a character, or a Multiple that contains a character and it's count (as an Int)

What encodeDirect does is actually parses a list of Chars (which, in Haskell, can be represented as a String, like "aabbcccd") into a list that looks something like this:

[Multiple 2 a, Multiple 2 b, Multiple 3 c, Single d]

The procedure is as follows:

First, we use encode every character in our input set by using a foldr and an encode function in order to get a list that contains 2-tuples with our character as the second value, and its count as the first. (   [(2, 'a'), (2, 'b') ... ]   )

The encode function might look a little cryptic, but broken down, it makes sense. First, if we have an empty resultant list of Counts, we need to put the first character we encounter in the resultant list. Once we have a resultant list (no matter how small), we are able to encode the other values by following some logic:
1. If the first character value in the resultant list matches what we are currently trying encode, we simply need to step up the count on that entry.
2. Otherwise, we need to add the new character to the front of the list with a count of 1.

When the foldr is complete, we have a nice list that looks just like how I described previously.

Now, to get everything wrapped up into a Count declaration, we simply map the toCount function over the list we just generated. The toCount function takes one of our 2-tuple values and creates a Single value out of it if its count is equivalent to 1, otherwise it packs it into a Multiple value.

Once this is mapped, we have our resultant list!

encodeDirect "aabbcccd" = [Multiple 2 a, Multiple 2 b, Multiple 3 c, Single d] 

PS:I picked up a bit of new syntax from a video I watched last night, located here:  Sokoban Live Coding. I learned a lot from it. If you're interested in Haskell, check it out.

Until next time!