Two Guys Arguing

rock smashes scissors

Posted in haskell by youngnh on 01.27.10

as simple as A -> B -> C

So, almost two months ago I issued a challenge to Ben to implement a silly spec of a problem I had recently been playing around with. The response and the knowledge I got out of this has been tremendous.

Kevin Berridge wrote an implementation.
Josh Schramm started his own fork.
Ben, my co-blogger, wrote his own implementation.
Heath Borders wrote an implementation and then gave a fantastic presentation on his solution, which sparked a lot of discussion amongst some very smart folks at our office.

I first implemented this in Haskell. It took me a shade under 2 hours and came in at 100 lines of code even. Prodding from the peanut gallery on twitter eventually led me to cut even that number by 25 lines.

To my eye, the solution that I came up was eminently readable, flexible, and precisely solved the problem with no bloat. What amazed me more, was that this was my first try at the problem. I’ve produced code I fell in love with on more than one occasion and in more than one language, but never on the first try. Something about Haskell made turning thoughts and words into working software immensely easy.

I think it is Haskell’s type declarations. Originally, before anybody else had written their implementations, I conceived of this challenge as a way of showing how cool and natural and easy it is to go from a series of type declarations to a fully working program. This was my thought process while writing my Haskell RPS:

The two basic datatypes are Player, which is a container type for a name, and Throw of which there are Rock, Paper and Scissors specializations. Everything else comes from that.

A Haskell type declaration looks like this:


A -> B -> C

This declaration describes a function that takes a type A, a type B and returns a type C.

If you want to display a message to the user? Haskell has a type signature for that:


String -> IO ()

The IO () part is a peculiarity of Haskell’s purity. It basically says that nothing is returned, that’s the () part, but that input and output have been performed, that’s the IO part.

Now, say you want to read that string back into an object your program can use?


(Read a) => String -> a

This signature says that given a String, the function will return a type that implements the Read typeclass. Read is most like a Java interface, but the function implementing this type declaration would utilize it using techniques more akin to Java generics.

Those two functions can then be combined into a function that takes a prompt string and returns an object:


(Read a) => String -> IO a

What the above signature says is that, given a string, this function will perform IO and return any type that implements Read. Exactly which type that is depends on the context the function is used in. That the same function depending on how it is used can return any conforming datatype, is the true power of generics and type inference.

This signature really encompasses the first couple of lines of the spec. By implementing the Read typeclass for Player and Throw, we can now prompt the user and get back Player and Throw objects that we can then go on to do processing with. Being able to prompt and read in responses gets us halfway through the spec. Halfway!

What’s left is to define when a player has won and to play the game until that situation occurs. There are a couple of ways you could choose to determine a winner, but my type signature would look like this:


(Player, Integer) -> (Player, Integer) -> Maybe Player

Which says that given a tuple for each player and their score, you may or may not be able to return a winner. The cool part is that the “may not” part is the same type as the “may” part, which makes handling each case super-explicit and easy to follow.

With how to win the game in place, finally, it is time to implement the overall game. Here’s the signature I came up with:


WinLogic -> (Player, [Throw]) -> (Player, [Throw]) -> Player

I called the operation of determining a winner WinLogic. This says that if you can pass in a WinLogic object and a tuple of each player and all of their throws, then you can finally return a winning player. You’re thinking, wait, how can you pass in all of a player’s throws if they won’t have given them to you until the game’s over? Well, that’s where Haskell’s lazy evaluation makes things easy, but it’s really no more magic than passing an Iterator object in Java.

With a few extra flourishes, the Haskell implementation is done. This is the post that I had written in my mind when I first issued my co-blogger the Rock Paper Scissors challenge. Of course, what happened after made things a bit messier, and there’s some other interesting lessons to learn from everybody else’s efforts, so I’ll cover some of the ensuing happenings in later posts.

Follow

Get every new post delivered to your Inbox.